栈（stack） 是很简单的⼀种数据结构， 先进后出的逻辑顺序， 符合某些问题的特点， ⽐如说函数调⽤栈。

单调栈实际上就是栈， 只是利⽤了⼀些巧妙的逻辑， 使得每次新元素⼊栈后， 栈内的元素都保持有序（单调递增或单调递减） 。

听起来有点像堆（heap） ？ 不是的， 单调栈⽤途不太⼴泛， 只处理⼀种典型的问题， 叫做 Next Greater Element。 本⽂⽤讲解单调队列的算法模版解决这类问题， 并且探讨处理「循环数组」 的策略。

⾸先， 讲解 Next Greater Number 的原始问题： 给你⼀个数组， 返回⼀个等⻓的数组， 对应索引存储着下⼀个更⼤元素， 如果没有更⼤的元素， 就存-1。 不好⽤语⾔解释清楚， 直接上⼀个例⼦：给你⼀个数组 [2,1,2,4,3]， 你返回数组 [4,2,4,-1,-1]。

解释： 第⼀个 2 后⾯⽐ 2 ⼤的数是 4; 1 后⾯⽐ 1 ⼤的数是 2； 第⼆个 2 后⾯⽐ 2 ⼤的数是 4; 4 后⾯没有⽐ 4 ⼤的数， 填 -1； 3 后⾯没有⽐ 3 ⼤的数， 填-1。

这道题的暴⼒解法很好想到， 就是对每个元素后⾯都进⾏扫描， 找到第⼀个更⼤的元素就⾏了。 但是暴⼒解法的时间复杂度是 O(n^2)。

这个问题可以这样抽象思考： 把数组的元素想象成并列站⽴的⼈， 元素⼤⼩想象成⼈的⾝⾼。 这些⼈⾯对你站成⼀列， 如何求元素「2」 的 Next GreaterNumber 呢？ 很简单， 如果能够看到元素「2」 ， 那么他后⾯可⻅的第⼀个⼈就是「2」 的 Next Greater Number， 因为⽐「2」 ⼩的元素⾝⾼不够， 都被「2」 挡住了， 第⼀个露出来的就是答案。

这个情景很好理解吧？ 带着这个抽象的情景， 先来看下代码。

vector nextGreaterElement(vector& nums) {
vector ans(nums.size()); // 存放答案的数组
stack s;
for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈⾥放
while (!s.empty() && s.top() <= nums[i]) { // 判定个⼦⾼矮
s.pop(); // 矮个起开， 反正也被挡着了。 。 。
} a
ns[i] = s.empty() ? -1 : s.top(); // 这个元素⾝后的第⼀个⾼个
s.push(nums[i]); // 进队， 接受之后的⾝⾼判定吧！
} r
eturn ans;
}

这就是单调队列解决问题的模板。 for 循环要从后往前扫描元素， 因为我们借助的是栈的结构， 倒着⼊栈， 其实是正着出栈。 while 循环是把两个“⾼个”元素之间的元素排除， 因为他们的存在没有意义， 前⾯挡着个“更⾼”的元素， 所以他们不可能被作为后续进来的元素的 Next Great Number 了。

这个算法的时间复杂度不是那么直观， 如果你看到 for 循环嵌套 while 循环， 可能认为这个算法的复杂度也是 O(n^2)， 但是实际上这个算法的复杂度只有 O(n)。

分析它的时间复杂度， 要从整体来看： 总共有 n 个元素， 每个元素都被push ⼊栈了⼀次， ⽽最多会被 pop ⼀次， 没有任何冗余操作。 所以总的计算规模是和元素规模 n 成正⽐的， 也就是 O(n) 的复杂度。

现在， 你已经掌握了单调栈的使⽤技巧， 来⼀个简单的变形来加深⼀下理解。

给你⼀个数组 T = [73, 74, 75, 71, 69, 72, 76, 73]， 这个数组存放的是近⼏天的天⽓⽓温（这⽓温是铁板烧？ 不是的， 这⾥⽤的华⽒度） 。 你返回⼀个数组， 计算： 对于每⼀天， 你还要⾄少等多少天才能等到⼀个更暖和的⽓温；如果等不到那⼀天， 填 0 。

举例： 给你 T = [73, 74, 75, 71, 69, 72, 76, 73]， 你返回 [1, 1, 4, 2, 1, 1, 0, 0]。

解释： 第⼀天 73 华⽒度， 第⼆天 74 华⽒度， ⽐ 73 ⼤， 所以对于第⼀天，只要等⼀天就能等到⼀个更暖和的⽓温。 后⾯的同理。

你已经对 Next Greater Number 类型问题有些敏感了， 这个问题本质上也是找 Next Greater Number， 只不过现在不是问你 Next Greater Number 是多少， ⽽是问你当前距离 Next Greater Number 的距离⽽已。

相同类型的问题， 相同的思路， 直接调⽤单调栈的算法模板， 稍作改动就可以啦， 直接上代码把。

vector dailyTemperatures(vector& T) {
vector ans(T.size());
stack s; // 这⾥放元素索引， ⽽不是元素
for (int i = T.size() - 1; i >= 0; i--) {
while (!s.empty() && T[s.top()] <= T[i]) {
s.pop();
} a
ns[i] = s.empty() ? 0 : (s.top() - i); // 得到索引间距
s.push(i); // 加⼊索引， ⽽不是元素
} r
eturn ans;
}

单调栈讲解完毕。 下⾯开始另⼀个重点： 如何处理「循环数组」 。

同样是 Next Greater Number， 现在假设给你的数组是个环形的， 如何处理？给你⼀个数组 [2,1,2,4,3]， 你返回数组 [4,2,4,-1,4]。 拥有了环形属性， 最后⼀个元素 3 绕了⼀圈后找到了⽐⾃⼰⼤的元素 4 。

⾸先， 计算机的内存都是线性的， 没有真正意义上的环形数组， 但是我们可以模拟出环形数组的效果， ⼀般是通过 % 运算符求模（余数） ， 获得环形特效：

回到NextGreaterNumber的问题，增加了环形属性后，问题的难点在于：这个Next的意义不仅仅是当前元素的右边了，有可能出现在当前元素的左边（如上例）。

明确问题，问题就已经解决了⼀半了。我们可以考虑这样的思路：将原始数组“翻倍”，就是在后⾯再接⼀个原始数组，这样的话，按照之前“⽐⾝⾼”的流程，每个元素不仅可以⽐较⾃⼰右边的元素，⽽且也可以和左边的元素⽐较了。

怎么实现呢？你当然可以把这个双倍⻓度的数组构造出来，然后套⽤算法模板。但是，我们可以不⽤构造新数组，⽽是利⽤循环数组的技巧来模拟。

查看完整代码，获取Java数据结构与算法全新全套左神算法教程，请私信或评论留言。