# 数据结构：单调栈

## 柱状图中最大的矩形

### 思路详解

`1 2 5 1 6 3` 为例。

`````` 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
``````

### 代码

`````` 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`

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

### 代码

`````` 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 = [73,74,75,71,69,72,76,73]

``````

### 思路详解

• 如果元素在末尾，那么后面肯定不会有更大的，就填 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

496. 下一个更大元素 I - 力扣（LeetCode）

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

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