496. Next Greater Element I 

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) {
        Map<Integer, Integer> valueToGreaterElementMap = new HashMap<>();
        Stack<Integer> decreaseStack = new Stack<>(); // 单调递减栈
        for (int num : nums2) {
            while (!decreaseStack.isEmpty() && num > decreaseStack.peek()) {
                // 出现了更大的值
                valueToGreaterElementMap.put(decreaseStack.pop(), num);
            }

            decreaseStack.push(num);
        }

        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = valueToGreaterElementMap.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

References

496. Next Greater Element I