496. 下一個更大元素 I
給你兩個 沒有重復元素 的數組?nums1 和?nums2?，其中nums1?是?nums2?的子集。
請你找出 nums1?中每個元素在?nums2?中的下一個比其大的值。
nums1?中數字?x?的下一個更大元素是指?x?在?nums2?中對應位置的右邊的第一個比?x?大的元素。如果不存在，對應位置輸出 -1 。
示例 1:輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:對于 num1 中的數字 4 ，你無法在第二個數組中找到下一個更大的數字，因此輸出 -1 。對于 num1 中的數字 1 ，第二個數組中數字1右邊的下一個較大數字是 3 。對于 num1 中的數字 2 ，第二個數組中沒有下一個更大的數字，因此輸出 -1 。示例 2:輸入: nums1 = [2,4], nums2 = [1,2,3,4].
輸出: [3,-1]
解釋:對于 num1 中的數字 2 ，第二個數組中的下一個較大數字是 3 。對于 num1 中的數字 4 ，第二個數組中沒有下一個更大的數字，因此輸出 -1 。
提示：
-
1 <= nums1.length <= nums2.length <= 1000
-
0 <= nums1[i], nums2[i] <= 10^4
-
nums1和nums2中所有整數 互不相同
-
nums1 中的所有整數同樣出現在 nums2 中
-
進階：你可以設計一個時間復雜度為 O(nums1.length + nums2.length) 的解決方案嗎？
解題思路
- 為了在遍歷nums2中元素時，可以快速定位到其在nums1中的對應下標，使用map記錄下nums1中元素和對應下標的映射關系，當計算nums2中元素時，可以直接獲取到需要填入結果數組的下標
- 使用單調遞增的棧維護，棧頂元素的值是最小的，當遍歷到nums2[i]時，處于i右邊區間元素的遞增序列，通過查找遞增序列中大于nums2[i]的元素，該元素就是右邊的第一個比 nums2[i] 大的元素
代碼
func nextGreaterElement(nums1 []int, nums2 []int) []int {m := make(map[int]int,len(nums1))for i := range nums1 {m[nums1[i]]=i}res:= make([]int, len(nums1))stack:= make([]int,0)for i := len(nums2)-1; i >=0 ; i-- {for len(stack)>0&&nums2[i]>=stack[len(stack)-1] {stack=stack[:len(stack)-1]}idx,ok := m[nums2[i]]if ok{if len(stack)==0 {res[idx]=-1}else {res[idx]=stack[len(stack)-1]}}stack = append(stack, nums2[i])}return res
}
函數)
