LeetCode link

Intuition

  • Using a descending stack to maintain the numbers.
  • When the current number is larger than the top, this number is the next-greater-element of the top. Using a map to index it.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int[] result = new int[n1];
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                int top = stack.pop();
                map.put(top, nums2[i]);
            }
            stack.push(nums2[i]);
        }
        for (int i = 0; i < n1; i++) {
            result[i] = map.getOrDefault(nums1[i], -1);
        }
        return result;
    }
}