LeetCode 503. Next bigger Element II

503. Next bigger element II

 

【 Monotonic stack 】 Put those elements before the last element on the stack first , Form a ring , Then follow the monotonic stack method to traverse ：

That is, for each element i, Put all the elements smaller than him out of the stack , At this time, if there is still , Then the top of the stack is the first one bigger than him , If it is empty, it means there is no . Finally, don't forget to put the elements i Push .

class Solution {
    //  Monotonic stack  3:15 3:24
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new LinkedList();
        int i, j, n = nums.length;
        for (i = n - 2; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            stack.push(nums[i]);
        }
        int[] ans = new int[n];
        for (i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) {
                ans[i] = -1;
            } else {
                ans[i] = stack.peek();
            }
            stack.push(nums[i]);
        }
        return ans;
    }
}