数据结构：单调栈
柱状图中最大的矩形
思路详解
以 1 2 5 1 6 3 为例。
假设新元素入栈不破坏单调性，那么就让它的坐标入栈。
刚开始我们处于 i = 0 的位置。发现三个连续单增项，让其下标入栈。
因此得到下标 0 1 2对应 1 2 5，这时候再进入下一个元素—— 1 会导致单调性破坏。
因此开始出栈。
首先 5 出栈，其面积结算为 5。（面积怎么算的：用 i 作为右边界，用栈顶元素 stk.top()+1 作为左边界，我们会发现面积夹在中间，如下图红色所示。宽度为右边界减去左边界+1，即 i - stk.top() - 1。高度则为 height[outidx]，即 5.）
然后栈顶变成 2, 还是大于将来的 1. 因此开始出栈，2 出栈，其面积结算为4
我们要求严格单增，所以 1 也要出栈。结算 4 面积。
之后是一波增长红利期，1、6 的下标入栈。
遇到了 3，无法增长，开始结算。6 被结算得 6.
此时 3 可以入队了。同时遇到空气墙。
结算 3， 得到 6
最后一步 栈空了，此时应当以 0 作为左边界（否则遇到 {2 1 2} 这种输入就要被坑）结算得到 6.
在上述结算面积中，最大的是 6.
上述过程的日志如下：
1push 0(1)
2push 1(2)
3push 2(5)
4pop 2(5)
5width = 1
6area = 5
7
8pop 1(2)
9width = 2
10area = 4
11
12pop 0(1)
13width = 3
14area = 3
15
16push 3(1)
17push 4(6)
18pop 4(6)
19width = 1
20area = 6
21
22push 5(3)
23pop 5(3)
24width = 2
25area = 6
26
27pop 3(1)
28width = 6
29area = 6
30
316
代码
如果用上面的思路直接写代码，会发现如果遇到 2 1 2 这种输入就会算错。原因在于，如果栈已经空了，
1 int largestRectangleArea(vector<int>& heights) {
2 int n = static_cast<int>(heights.size()), maxarea = 0;
3 heights.push_back(0);
4 stack<int> stk;
5 int i = 0;
6 do {
7 while (stk.empty() || heights[stk.top()] < heights[i]) {
8 stk.push(i++);
9 }
10 auto outidx = stk.top(); stk.pop();
11 auto width = stk.empty() ? i : i - stk.top() - 1;
12 maxarea = max(width * heights[outidx], maxarea);
13 } while (i < n || !stk.empty());
14 return maxarea;
15 }
注意事项
-
向
heights末尾推个 0, 这样能促使末尾增长序列的结算。 -
注意条件是
heights[stk.top()] < heights[i]很容易漏写成stk.top() < heights[i]非常难调试 -
当栈空了的时候，应当以 0 作为左边界。
-
栈空了，程序也不一定结束。
-
注意循环条件 是
i < n或!stack.empty()
下面是两种带详细输出的写法，如果看不懂别人的解析，很正常，建议结合输出理解。
1class Solution {
2 public:
3 int largestRectangleArea(vector<int>& heights) {
4 int n = static_cast<int>(heights.size()), maxarea = 0;
5 heights.push_back(0);
6 stack<int> stk;
7 int i = 0;
8 do {
9 while (stk.empty() || heights[stk.top()] < heights[i]) {
10 stk.push(i);
11 std::cout << "push " << i << "(" << heights[i] << ")" << std::endl;
12 i++;
13 }
14 auto outidx = stk.top();
15 stk.pop();
16 auto out = heights[outidx];
17 std::cout << "pop " << outidx << "(" << heights[outidx] << ")"
18 << std::endl;
19 auto width = stk.empty() ? i : i - stk.top() - 1;
20 printf("width = %d\n", width);
21 auto area = width * out;
22 std::cout << "area = " << area << std::endl;
23
24 maxarea = max(area, maxarea);
25 std::cout << std::endl;
26 } while (i < n || !stk.empty());
27 return maxarea;
28 }
29
30 int largestRectangleArea2(vector<int>& heights) {
31 stack<int> stk;
32 int maxArea = 0;
33 heights.push_back(0);
34 for (int i = 0; i < heights.size(); i++) {
35 while (!stk.empty() && heights[i] < heights[stk.top()]) {
36 auto height = heights[stk.top()];
37 std::cout << "pop " << stk.top() << "(" << height << ")" << std::endl;
38 stk.pop();
39
40 int width = stk.empty() ? i : i - stk.top() - 1;
41 printf("width = %d\n", width);
42 printf("area = %d\n", height * width);
43 std::cout << std::endl;
44 maxArea = max(maxArea, height * width);
45 }
46 stk.push(i);
47 std::cout << "push " << i << "(" << heights[i] << ")" << std::endl;
48 }
49
50 return maxArea;
51 }
52};
接雨水
思路详解
我们采用单调递减栈。雨水面积的计算通过归纳可以得到。下面介绍思路是怎么想到的：
对照上图。我们依然是先一股脑入栈，然后出栈结算。结算时面积计算原理如下：
-
宽度：取决于当前位置和栈顶下标的距离。例如我们出栈 1 位置的红色矩形时，当前 i=2，栈顶是最左边的矩形，其下标是 0. 因此之间的距离是
i - (0+1) = 1 -
高度：首先，当前位置的高度和栈顶元素的高度，二者取最小值，作为绝对高度。再减去当前元素的高度，得到相对高度。
为什么宽度不是恒定为 1 呢？ 考虑下面的情况。则结算的面积依次是 B 和 A，可以发现宽度是不同的。
代码
1class Solution {
2 public:
3 int trap(vector<int>& heights) {
4 int trapsum = 0, i = 0;
5 int n = static_cast<int>(heights.size());
6 heights.push_back(0);
7 stack<int> stk;
8 do {
9 while (i < n && (stk.empty() || (heights[stk.top()] > heights[i]))) {
10 stk.push(i++);
11 }
12 auto outidx = stk.top();
13 stk.pop();
14 auto height = min(stk.empty() ? 0 : heights[stk.top()], heights[i]) -
15 heights[outidx];
16 auto width = stk.empty() ? 0 : i - stk.top() - 1;
17 trapsum += max(height * width, 0);
18 } while (i < n || !stk.empty());
19 return trapsum;
20 }
21};
注意事项
-
相比于柱状图最大矩形问题，此题注意
while的条件增加了对i < n的限制。 -
当栈空时，取绝对高度为 0
-
高度可能出现负数，因此与 0 做 max。
trapsum += max(height * width, 0)
每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
思路详解
暴力法是非常简单的。即对每个位置，向后搜索一遍。复杂度过高。我们尝试单调递减栈：单调入栈，然后出栈时计算距离，存入被出栈元素下标的返回数组。
关键在于距离怎么算。
-
如果元素在末尾，那么后面肯定不会有更大的，就填 0
-
如果在中间，则距离是当前位置 i 减去出栈元素位置
代码
1 vector<int> dailyTemperatures(vector<int>& nums) {
2 int i = 0, n = static_cast<int>(nums.size());
3 std::vector<int> ret(n, -1);
4 stack<int> stk;
5 do {
6 while (i < n && (stk.empty() || (nums[stk.top()] >= nums[i]))) {
7 stk.push(i++);
8 }
9 auto outidx = stk.top();
10 stk.pop();
11 ret[outidx] = i == n ? 0 : i - outidx;
12 } while (!stk.empty() || i < n);
13 return ret;
14 }
注意事项
-
注意我们要找的是下个更大的元素，因此不要严格递减。递减条件为
nums[stk.top()] >= nums[i] -
处理末尾元素是个坑
下一个更大元素 I
1class Solution {
2public:
3 vector<int> nextGreaterElement(vector<int>& query, vector<int>& nums) {
4 map<int,int> num2idx;
5 for (size_t i = 0; i < nums.size(); i++) {
6 num2idx[nums[i]] = i;
7 }
8
9 //--BEGIN--
10 stack<int> incr_stk;
11 vector<int> ngn(nums.size());
12 for(int i = nums.size() - 1; i >= 0; i--) {
13 // 过滤
14 while(!incr_stk.empty() && incr_stk.top() <= nums[i]) {
15 incr_stk.pop();
16 }
17 // 求解
18 ngn[i] = incr_stk.empty() ? -1 : incr_stk.top();
19
20 incr_stk.push(nums[i]);
21 }
22 //--END--
23 vector<int> ret(query.size());
24 for (int i = 0; i < query.size(); i++){
25 ret[i] = ngn[num2idx[query[i]]];
26 }
27 return ret;
28 }
29};
496. 下一个更大元素 I 907. 子数组的最小值之和 1124. 表现良好的最长时间段 2334. 元素值大于变化阈值的子数组 2281. 巫师的总力量和