栈（stack）是很简单的一种数据结构，先进后出的逻辑顺序，符合某些问题的特点，比如说函数调用栈。单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

听起来有点像堆（heap）？但实际上不是。

时间复杂度：由于每个元素只有一次入栈和出栈的操作，所以 单调栈的维护时间复杂度是 O(n)。

单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等。

int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>(); 
    // 倒着往栈里放
    for (int i = n - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.isEmpty() && s.peek() <= nums[i]) {
            s.pop();
        }
        // nums[i] 身后的更大元素
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

同样是求下一个更大元素，现在假设给你的数组是个环形的，如何处理？力扣第 503 题「下一个更大元素 II」就是这个问题：输入一个「环形数组」，请你计算其中每个元素的下一个更大元素。

比如输入 [2,1,2,4,3]，你应该返回 [4,2,4,-1,4]，因为拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。

我们一般是通过 % 运算符求模（余数），来模拟环形特效：

int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
    // 在环形数组中转圈
    print(arr[index % n]);
    index++;
}

这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是 [2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为下一个更大元素。

对于这种需求，常用套路就是将数组长度翻倍：

这样，元素 3 就可以找到元素 4 作为下一个更大元素了，而且其他的元素都可以被正确地计算。

有了思路，最简单的实现方式当然可以把这个双倍长度的数组构造出来，然后套用算法模板。但是，我们可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。直接看代码吧：

int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>();
    // 数组长度加倍模拟环形数组
    for (int i = 2 * n - 1; i >= 0; i--) {
        // 索引 i 要求模，其他的和模板一样
        while (!s.isEmpty() && s.peek() <= nums[i % n]) {
            s.pop();
        }
        res[i % n] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i % n]);
    }
    return res;
}

这样，就可以巧妙解决环形数组的问题，时间复杂度 O(N)。

• 496. 下一个更大元素 I
• 503. 下一个更大元素 II

• 特殊数据结构：单调栈