# 0503. Next Greater Element II
###### tags: `Leetcode` `单调栈`
Link: https://leetcode-cn.com/problems/next-greater-element-ii/

## 思路
最简单的思路还是暴力枚举。对于每个数而言，我们需要遍历其右边的数，直到找到比自身大的数，这是一个$O(N^2)$的做法。之所以是$O(N^2)$，是因为每次找下一个最大值，我们是通过「主动」遍历来实现的。

但，对于「找最近一个比当前值大/小」的问题，都可以使用<font size=6, color=green>**单调栈**</font>来解决。

如果使用的是<font size=6, color=red>**单调栈**</font>的话，可以做到<font size=6, color=blue>**$O(N)$**</font>的复杂度，我们将当前还没得到答案的下标暂存于栈内，从而实现「被动」更新答案。

也就是说，栈内存放的永远是还没更新答案的下标。

具体的做法是：

建立「单调递减栈」，并对原数组遍历一次：

- 如果栈为空，则把当前元素放入栈内；
- 如果栈不为空，则需要判断当前元素和栈顶元素的大小：
* 如果当前元素比栈顶元素大：说明当前元素是前面一些元素的「下一个更大元素」，则**逐个弹出**栈顶元素，直到当前元素比栈顶元素**小为止**。
* 如果当前元素比栈顶元素小：说明当前元素的「**下一个更大元素**」与栈顶元素相同，则把当前元素入栈。

## Code in Java

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int [] res = new int[n];
        Arrays.fill(res, -1);
        // Stack <Integer> stack = new Stack<>();
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n*2; i++){
            int num = nums[i % n];
            while(!deque.isEmpty() && num > nums[deque.peekLast()]){
                res[deque.pollLast()] = num;
            }
            if(i < n) deque.addLast(i);
        }
        return res;
    }
}