# 如何使用单调栈解题
![](../pictures/souyisou.png)
相关推荐:
* [回溯算法解题套路框架](https://labuladong.gitbook.io/algo/)
* [动态规划解题套路框架](https://labuladong.gitbook.io/algo/)
读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目:
[496.下一个更大元素I](https://leetcode-cn.com/problems/next-greater-element-i)
[503.下一个更大元素II](https://leetcode-cn.com/problems/next-greater-element-ii)
[739.每日温度](https://leetcode-cn.com/problems/daily-temperatures/)
**-----------**
栈(stack)是很简单的一种数据结构,先进后出的逻辑顺序,符合某些问题的特点,比如说函数调用栈。
单调栈实际上就是栈,只是利用了一些巧妙的逻辑,使得每次新元素入栈后,栈内的元素都保持有序(单调递增或单调递减)。
听起来有点像堆(heap)?不是的,单调栈用途不太广泛,只处理一种典型的问题,叫做 Next Greater Element。本文用讲解单调队列的算法模版解决这类问题,并且探讨处理「循环数组」的策略。
### 单调栈模板
首先,看一下 Next Greater Number 的原始问题,这是力扣第 496 题「下一个更大元素 I」:
给你一个数组,返回一个等长的数组,对应索引存储着下一个更大元素,如果没有更大的元素,就存 -1。
函数签名如下:
```cpp
vector nextGreaterElement(vector& nums);
```
比如说,输入一个数组 `nums = [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 Greater Number 呢?很简单,如果能够看到元素「2」,那么他后面可见的第一个人就是「2」的 Next Greater Number,因为比「2」小的元素身高不够,都被「2」挡住了,第一个露出来的就是答案。
![](../pictures/%E5%8D%95%E8%B0%83%E6%A0%88/1.jpeg)
这个情景很好理解吧?带着这个抽象的情景,先来看下代码。
```cpp
vector nextGreaterElement(vector& nums) {
vector res(nums.size()); // 存放答案的数组
stack s;
// 倒着往栈里放
for (int i = nums.size() - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.empty() && s.top() <= nums[i]) {
// 矮个起开,反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的 next great number
res[i] = s.empty() ? -1 : s.top();
//
s.push(nums[i]);
}
return res;
}
```
这就是单调队列解决问题的模板。for 循环要从后往前扫描元素,因为我们借助的是栈的结构,倒着入栈,其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除,因为他们的存在没有意义,前面挡着个「更高」的元素,所以他们不可能被作为后续进来的元素的 Next Great Number 了。
这个算法的时间复杂度不是那么直观,如果你看到 for 循环嵌套 while 循环,可能认为这个算法的复杂度也是 `O(n^2)`,但是实际上这个算法的复杂度只有 `O(n)`。
分析它的时间复杂度,要从整体来看:总共有 `n` 个元素,每个元素都被 `push` 入栈了一次,而最多会被 `pop` 一次,没有任何冗余操作。所以总的计算规模是和元素规模 `n` 成正比的,也就是 `O(n)` 的复杂度。
### 问题变形
单调栈的使用技巧差不多了,来一个简单的变形,力扣第 739 题「每日温度」:
给你一个数组 `T`,这个数组存放的是近几天的天气气温,你返回一个等长的数组,计算:**对于每一天,你还要至少等多少天才能等到一个更暖和的气温;如果等不到那一天,填 0**。
函数签名如下:
```cpp
vector dailyTemperatures(vector& T);
```
比如说给你输入 `T = [73,74,75,71,69,76]`,你返回 `[1,1,3,2,1,0]`。
解释:第一天 73 华氏度,第二天 74 华氏度,比 73 大,所以对于第一天,只要等一天就能等到一个更暖和的气温,后面的同理。
这个问题本质上也是找 Next Greater Number,只不过现在不是问你 Next Greater Number 是多少,而是问你当前距离 Next Greater Number 的距离而已。
相同的思路,直接调用单调栈的算法模板,稍作改动就可以,直接上代码吧:
```cpp
vector dailyTemperatures(vector& T) {
vector res(T.size());
// 这里放元素索引,而不是元素
stack s;
/* 单调栈模板 */
for (int i = T.size() - 1; i >= 0; i--) {
while (!s.empty() && T[s.top()] <= T[i]) {
s.pop();
}
// 得到索引间距
res[i] = s.empty() ? 0 : (s.top() - i);
// 将索引入栈,而不是元素
s.push(i);
}
return res;
}
```
单调栈讲解完毕,下面开始另一个重点:如何处理「循环数组」。
### 如何处理环形数组
同样是 Next Greater Number,现在假设给你的数组是个环形的,如何处理?力扣第 503 题「下一个更大元素 II」就是这个问题:
比如输入一个数组 `[2,1,2,4,3]`,你返回数组 `[4,2,4,-1,4]`。拥有了环形属性,**最后一个元素 3 绕了一圈后找到了比自己大的元素 4**。
一般是通过 % 运算符求模(余数),来获得环形特效:
```java
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 作为 Next Greater Number。
**对于这种需求,常用套路就是将数组长度翻倍**:
![](../pictures/%E5%8D%95%E8%B0%83%E6%A0%88/2.jpeg)
这样,元素 3 就可以找到元素 4 作为 Next Greater Number 了,而且其他的元素都可以被正确地计算。
有了思路,最简单的实现方式当然可以把这个双倍长度的数组构造出来,然后套用算法模板。但是,**我们可以不用构造新数组,而是利用循环数组的技巧来模拟数组长度翻倍的效果**。
直接看代码吧:
```cpp
vector nextGreaterElements(vector& nums) {
int n = nums.size();
vector res(n);
stack s;
// 假装这个数组长度翻倍了
for (int i = 2 * n - 1; i >= 0; i--) {
// 索引要求模,其他的和模板一样
while (!s.empty() && s.top() <= nums[i % n])
s.pop();
res[i % n] = s.empty() ? -1 : s.top();
s.push(nums[i % n]);
}
return res;
}
```
这样,就可以巧妙解决环形数组的问题,时间复杂度 `O(N)`。
如果本文对你有帮助,请三连,这次一定。
**_____________**
**刷算法,学套路,认准 labuladong,公众号和 [在线电子书](https://labuladong.gitbook.io/algo/) 持续更新最新文章**。
**本小抄即将出版,微信扫码关注公众号,后台回复「小抄」限时免费获取,回复「进群」可进刷题群一起刷题,带你搞定 LeetCode**。
======其他语言代码======
### java
[ZakAnun](https://github.com/ZakAnun) 提供代码
```java
// 496.下一个更大元素
// 暴力解法
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
// 需要记录第一个数组每个元素在第二个数组中出现的位置
int index = 0;
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j]) {
index = j;
break;
}
}
// 根据找到的位置往后遍历,若符合条件则记录到结果数组
for (int k = index; k < nums2.length; k++) {
if (nums2[k] > nums1[i]) {
result[i] = nums2[k];
break;
}
}
// 判断若对应位置结果依然为默认值,则将其修改为 -1
if (result[i] == 0) {
result[i] = -1;
}
}
return result;
}
// 分析: 暴力解法中需要确定数组1中每个元素在数组2中的下标而需要进行额外的遍历导致时间复杂度升高,
// 但若能够先罗列出全部的结果,然后从结果集中获取数组1中每个元素对应的下一个更大元素,就可以节省这部分时间(这里需要引用 HashMap 帮助我们记录结果,以便根据数组1获取。
// 单调栈解法
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack stack = new Stack <>();
HashMap map = new HashMap <>();
int[] result = new int[nums1.length];
for (int value : nums2) {
while (!stack.empty() && value > stack.peek()) {
map.put(stack.pop(), value);
}
stack.push(value);
}
while (!stack.empty()) {
map.put(stack.pop(), -1);
}
for (int i = 0; i < nums1.length; i++) {
result[i] = map.get(nums1[i]);
}
return result;
}
```
[ZakAnun](https://github.com/ZakAnun) 提供代码
```java
// 739. Daily Temperatures
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack stack = new Stack<>();
int[] ans = new int[T.length];
for (int i = 0; i < T.length; i++) {
// 如果压栈之后不满足单调递减,弹出元素,直至保持单调性
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int index = stack.pop();
// 被弹出的元素(T[index])都是小于当前的元素(T[i]),由于栈内元素单调递减,大于被弹出元素(index)的最近的就是当前元素(i)
ans[index] = i - index;
}
stack.push(i);
}
return ans;
}
}
```
[JiangangZhao](https://github.com/JiangangZhao)提供【503.下一个更大元素II】【java】
```java
class Solution {
public int[] nextGreaterElements(int[] nums) {
//数组长度
int n = nums.length;
//逻辑拼接,数组长度翻倍
int len = n*2 - 1;
//存储结果数组
int[] res = new int[n];
//存放索引,不是元素
LinkedList s = new LinkedList<>();
//从前往后遍历
for (int i = 0; i < len; ++i) {
//索引要取模
int val = nums[i % n];
//当前元素比栈顶元素大,即是栈顶元素的下一个更大的元素
while (!s.isEmpty() && val > nums[s.peek()]) {
res[s.pop()] = val;
}
//i