友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
496. Next Greater Element I
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of `nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.Note:
-
All elements in
nums1andnums2are unique. -
The length of both
nums1andnums2would not exceed 1000.
思路分析
单调栈
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 单调栈，参考模板，自己书写
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-05 22:40:25
*/
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Deque<Integer> stack = new LinkedList<>();
Map<Integer, Integer> big = new HashMap<>();
for (int i = nums2.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() < nums2[i]) {
stack.pop();
}
int val = stack.isEmpty() ? -1 : stack.peek();
big.put(nums2[i], val);
stack.push(nums2[i]);
}
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = big.get(nums1[i]);
}
return result;
}