1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] nextGreaterArr = new int[nums2.length];
Arrays.fill(nextGreaterArr, -1);
Stack<Integer> stack = new Stack<>();
Map<Integer, Integer> numIdxMap = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
nextGreaterArr[stack.pop()] = nums2[i];
}
stack.push(i);
numIdxMap.put(nums2[i], i);
}
int[] ans = new int[nums1.length];
for (int i = 0; i < ans.length; i++) {
ans[i] = nextGreaterArr[numIdxMap.get(nums1[i])];
}
return ans;
}
}
|
monotonic stack的经典用法. 这里是decreasing stack. 能够得到某个数字左侧比它大的数字中index最大的那个是谁. 同时, stack中的数字也能知道自己右侧比自己大的元素中index最小的那个是谁.
某个数字右侧比自己大, 就说明能成全自己. 于是我们每次遇到一个新数字, 就要看能把栈里的哪些数字给成全了.
时间复杂度: O(m + n) m和n分别是nums1和nums2的长度
空间复杂度: O(n) n是nums2的长度.
