本文最后更新于 501 天前,其中的信息可能已经有所发展或是发生改变。
思路
这类题有套路,需要用到单调栈。
上图中绿色item想找到下一个比它大的值,只需要和红色item比较就行,而不需要和紫色的item比较。所以我们需要维护一个单调递增的栈,保存红色的值。
通过依次比较,得出,5对应的答案是6。
下一个数字4,来寻求下一个比它大的值。
同样的,2比5小,在这个数据结构中没有意义,他应该在5存入数据结构时抛出。也就是说,在寻找下一个比它大的值的时候,只需要和栈顶比较,如果栈顶大,那栈顶就是答案。否则抛出栈顶,继续比较。找到答案后,并入栈。
题目
nums1
中数字 x
的 下一个更大元素 是指 x
在 nums2
中对应位置 右侧 的 第一个 比 x
大的元素。
给你两个 没有重复元素 的数组 nums1
和 nums2
,下标从 0 开始计数,其中nums1
是 nums2
的子集。
对于每个 0 <= i < nums1.length
,找出满足 nums1[i] == nums2[j]
的下标 j
,并且在 nums2
确定 nums2[j]
的 下一个更大元素 。如果不存在下一个更大元素,那么本次查询的答案是 -1
。
返回一个长度为 nums1.length
的数组 ans
作为答案,满足 ans[i]
是如上所述的 下一个更大元素 。
示例 1:
输入:nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出:[-1,3,-1] 解释:nums1 中每个值的下一个更大元素如下所述: - 4 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。 - 1 ,用加粗斜体标识,nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。
示例 2:
输入:nums1 = [2,4], nums2 = [1,2,3,4]. 输出:[3,-1] 解释:nums1 中每个值的下一个更大元素如下所述: - 2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。
提示:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1
和nums2
中所有整数 互不相同nums1
中的所有整数同样出现在nums2
中
进阶:你可以设计一个时间复杂度为 O(nums1.length + nums2.length)
的解决方案吗?
Related Topics
代码
func nextGreaterElement(nums1 []int, nums2 []int) []int {
resMap := make(map[int]int, len(nums2))
stack := make([]int, 0, len(nums2))
for i := len(nums2) - 1; i >= 0; i-- {
for len(stack) > 0 && nums2[i] >= stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
resMap[nums2[i]] = stack[len(stack)-1]
} else {
resMap[nums2[i]] = -1
}
stack = append(stack, nums2[i])
}
resArr := make([]int, 0, len(nums1))
for i := 0; i < len(nums1); i++ {
resArr = append(resArr, resMap[nums1[i]])
}
return resArr
}