数据结构:单调栈

柱状图中最大的矩形

思路详解

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};

接雨水

思路详解

我们采用单调递减栈。雨水面积的计算通过归纳可以得到。下面介绍思路是怎么想到的:

decrease-stack-Page-1.drawio

对照上图。我们依然是先一股脑入栈,然后出栈结算。结算时面积计算原理如下:

  • 宽度:取决于当前位置和栈顶下标的距离。例如我们出栈 1 位置的红色矩形时,当前 i=2,栈顶是最左边的矩形,其下标是 0. 因此之间的距离是 i - (0+1) = 1

  • 高度:首先,当前位置的高度和栈顶元素的高度,二者取最小值,作为绝对高度。再减去当前元素的高度,得到相对高度。

代码

 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]

  • 处理末尾元素是个坑

序号 题目 题解
1 42. 接雨水(困难) 暴力解法、优化、双指针、单调栈
2 739. 每日温度(中等) 暴力解法 + 单调栈
3 496. 下一个更大元素 I(简单) 暴力解法、单调栈
4 316. 去除重复字母(困难) 栈 + 哨兵技巧(Java、C++、Python)
5 901. 股票价格跨度(中等) 「力扣」第 901 题:股票价格跨度(单调栈)
6 402. 移掉K位数字
7 581. 最短无序连续子数组

496. 下一个更大元素 I 907. 子数组的最小值之和 1124. 表现良好的最长时间段 2334. 元素值大于变化阈值的子数组 2281. 巫师的总力量和

最近发布

要查看全部文章,请点击右上角“归档”,下面是最近发布的几篇日志