LeetCode 503. 下一个更大元素 II

503. 下一个更大元素 II

 

【单调栈】把最后一个元素之前的那些元素先入栈，形成环，再按照单调栈的方法遍历即可：

即对于每个元素i，把栈中比他小的元素全部出栈，此时如果栈顶还有，那么栈顶就是第一个比他大的，如果为空说明没有。最后不要忘了把元素i入栈。

class Solution {
    // 单调栈 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;
    }
}