单调栈

调栈（Monotonic Stack）

1. 前提条件

单调栈适用于这一类题,对于数组中每个元素：

寻找

左边第一个比它大

左边第一个比它小

右边第一个比它大

右边第一个比它小

例如：

739 每日温度

496 下一个更大元素

503 下一个更大元素 II

84 柱状图最大矩形

这些题都有一个共同特点：找最近满足条件的元素

2. 为什么需要单调栈？

例如：

73 74 75 71 69 72 76 73

题目：对于每一天

找右边第一个更高温度

例如：

73

↓

74

答案1

再例如：

71

↓

72

答案：2

最容易想到双循环

例如：

for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
...
}
}

复杂度O(n²)

如果n=100000就超时。

所以需要O(n)

3. 核心思想

栈里面保存还没有找到答案的元素

例如数组：

73 74 75

开始：73

右边不知道有没有更大的。

于是：73入栈。

继续：74

发现：74>73

说明：73终于找到答案。

于是：73出栈。

然后：74自己还不知道未来有没有更大的。

继续入栈。

这就是单调栈。

4. 为什么叫"单调"？

因为：栈里面一直保持一种顺序。

例如每日温度：

维护从栈底到栈顶单调递减

例如：

80

75

73

一直越来越小。

为什么？

因为来了76

以后：

80

75

73

73：没用了。
弹。

得到：

80

75

76：

继续比75大。

75：也弹。

得到：80

最后：76：

入栈。

得到：

80

76

还是：单调递减。

所以叫单调递减栈。

5. 栈里面放什么？

这是最容易错的地方。

不是温度。而是下标

例如：

73 74 75

栈：

放：

0

1

2

为什么？

因为最后答案要求距离。

例如2-0=2

如果只存73
不知道它在哪里。

所以必须存下标。

6. 固定模板
   for(int i=0;i<n;i++)
   {
   while(top!=-1 &&
   nums[i]>nums[stack[top]])
   {
   int index=stack[top--];

    ans[index]=i-index;
   

   }

   stack[++top]=i;
   }

以后看到右边第一个更大基本就是这个。

7. 每日温度代码（C）
   int* dailyTemperatures(int* temperatures,
   int temperaturesSize,
   int* returnSize)
   {
   *returnSize = temperaturesSize;

   int* ans =
   calloc(temperaturesSize,sizeof(int));

   int stack[100001];

   int top=-1;

   for(int i=0;i<temperaturesSize;i++)
   {
   while(top!=-1 &&
   temperatures[i]>
   temperatures[stack[top]])
   {
   int index=stack[top--];

        ans[index]=i-index;
    }
   
    stack[++top]=i;
   

   }

   return ans;
   }

8. 详细举例
   数组：

73 74 75 71 69 72 76 73

下标：

0 1 2 3 4 5 6 7

第一步
i=0

73

栈：空。

直接入栈。

stack

↓

0

第二步
i=1

74

比较：

74>73

说明：

73找到更高温度。

弹：0

答案：ans[0]=

1-0=1

然后：

1：

入栈。

stack

↓

1

第三步
i=2

75

比较：

75>74

弹：

1

得到：

ans[1]=2-1=1

然后：

2：

入栈。

stack

↓

2

第四步
71

比较：

71>75？

不是。

直接入栈。

2

3

注意：

这里栈：

对应：

75

71

还是递减。

第五步

69：

继续：

75

71

69

--第六步

来了：72

比较：

72>69

弹：69。

答案：5-4=1

继续：72>71

再弹。

答案：5-3=2

继续：72>75

不是。
停止。

然后：72：

入栈。

现在：

栈：

75

72

对应：

下标：

2

5

第七步

来了：76

一直弹。

76>72

弹

76>75

弹

得到：

ans[5]=1

ans[2]=4

最后：76：

入栈。

最后：

得到：

1

1

4

2

1

1

0

0

和题目：一致。

9. 为什么是 while？

例如：

80

75

73

来了：

90

如果：

if(...)

只能：

弹：

73

但是：

90：

还：

大于：

75。

还：

大于：

80。

所以：

必须：

一直弹。

因此：

必须：

while(...)

这和希尔排序那个 while 的思想有点像：满足条件时要连续处理，而不是只处理一次。

10. 时间复杂度为什么 O(n)？

很多人觉得：

while

是不是

O(n²)？

其实：

不是。

因为：

每个元素：

最多：

入栈一次

出栈一次

例如：

73：

入一次

弹一次

结束。

所以：

总操作：

2n

复杂度：

★★★★★

O(n)
11. 易错点
① 栈里面放的是下标，不是值。

② while，不是 if。

③ 维护的是单调递减栈（每日温度）。

④ 弹栈时更新的是被弹出的那个元素答案。

⑤ 栈里剩下的元素说明右边没有更大的，答案默认是0。
12. 单调栈总结（★★★★★）
单调栈

作用：

寻找

最近更大

最近更小

---

每日温度：

维护：

单调递减栈

---

栈里：

存下标

---

模板：

for(i)

while(当前更大)

    弹栈

    更新答案

入栈

---

复杂度：

O(n)

因为：

每个元素

最多：

入一次

出一次。
看一下灵神代码
写法一：从右到左
栈中记录下一个更大元素的「候选项」的下标。

每次循环，我们可以在「候选项」中找到答案。

class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0] * n
st = []
for i in range(n - 1, -1, -1):
t = temperatures[i]
while st and t >= temperatures[st[-1]]:
st.pop()
if st:
ans[i] = st[-1] - i
st.append(i)
return ans
复杂度分析
时间复杂度：O(n)，其中 n 为 temperatures 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。
空间复杂度：O(min(n,U))，其中 U=max(temperatures)−min(temperatures)+1。返回值不计入，仅考虑栈的最大空间消耗。

写法二：从左到右
栈中记录还没算出下一个更大元素的那些数的下标。

相当于栈是一个 todolist，在循环的过程中，现在还不知道答案是多少，在后面的循环中会算出答案。

class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0] * n
st = [] # todolist
for i, t in enumerate(temperatures):
//栈不为空并且该天温度值大于栈顶温度
while st and t > temperatures[st[-1]]:
j = st.pop()
ans[j] = i - j
st.append(i)
return ans
复杂度分析
时间复杂度：O(n)，其中 n 为 temperatures 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。
空间复杂度：O(n)。注意这种写法栈中可以有重复元素。

接雨水：
面的方法相当于「竖着」计算面积，单调栈的做法相当于「横着」计算面积。

这个方法可以总结成 16 个字：找上一个更大元素，在找的过程中填坑。

注意 while 中加了等号，这可以让栈中没有重复元素，从而在有很多重复元素的情况下，使用更少的空间。

看复杂度的话，单调栈不如双指针的做法。但如果输入的 height 是一个流（stream），只能从左到右遍历，那么单调栈（在这种场景下）就是不错的方法了。

class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
st = []
for i, h in enumerate(height):
while st and height[st[-1]] <= h:
bottom_h = height[st.pop()]
if not st: # 栈是空的
break
left = st[-1]
dh = min(height[left], h) - bottom_h # 面积的高
ans += dh * (i - left - 1)
st.append(i)
return ans

#define MIN(a, b) ((b) < (a) ? (b) : (a))

int trap(int* height, int heightSize) {
int ans = 0;

// 用数组模拟栈，栈大小最多为 heightSize
int* st = malloc(sizeof(int) * heightSize);
int top = -1; // 栈顶指针，初始为空栈

for (int i = 0; i < heightSize; i++) {
    int h = height[i];
    while (top >= 0 && height[st[top]] <= h) {
        int bottom_h = height[st[top]];
        top--; // 出栈
        if (top < 0) {
            break;
        }
        int left = st[top];
        int dh = MIN(height[left], height[i]) - bottom_h; // 面积的高
        ans += dh * (i - left - 1);
    }
    st[++top] = i; // 入栈
}

free(st);
return ans;