496. Next Greater Element I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> smallerToGreaterMap = new HashMap<>();
        Stack<Integer> decreaseStack = new Stack<>(); // 单调递减栈，栈中存储的为索引

        for (int i = 0; i < nums2.length; i++) {
            while (!decreaseStack.isEmpty() && nums2[i] > nums2[decreaseStack.peek()]) {
                // 遇到了更大的元素
                int smallerIndex = decreaseStack.pop();
                smallerToGreaterMap.put(nums2[smallerIndex], nums2[i]);
            }

            decreaseStack.push(i);
        }

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

Reference

496. Next Greater Element I