Monotonic Stack

✅ 单调栈相关例题

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img

1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

1️⃣ 单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int largestRectangleArea(vector<int> &heights) {
        int n = heights.size();
        vector<int> left(n, -1);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[i] <= heights[st.top()]) {
                st.pop();
            }
            if (!st.empty()) {
                left[i] = st.top();
            }
            st.push(i);
        }

        vector<int> right(n, n);
        st = stack<int>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && heights[i] <= heights[st.top()]) {
                st.pop();
            }
            if (!st.empty()) {
                right[i] = st.top();
            }
            st.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
};

42. 接雨水 （常用「相向双指针」方法）

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

1️⃣ 前后缀分离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pre_max(n); // pre_max[i] 表示从 height[0] 到 height[i] 的最大值
        pre_max[0] = height[0];
        for (int i = 1; i < n; i++) {
            pre_max[i] = max(pre_max[i - 1], height[i]);
        }

        vector<int> suf_max(n); // suf_max[i] 表示从 height[i] 到 height[n-1] 的最大值
        suf_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suf_max[i] = max(suf_max[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += min(pre_max[i], suf_max[i]) - height[i]; // 累加每个水桶能接多少水
        }
        return ans;
    }
};

2️⃣ 相向双指针（谁小谁移动）

利用这个思路可以完成「3D 接雨水」

注意 while 循环可以不加等号，因为在「谁小移动谁」的规则下，相遇的位置一定是最高的柱子，这个柱子是无法接水的。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, left = 0, right = height.size() - 1, pre_max = 0, suf_max = 0;
        while (left < right) {
            pre_max = max(pre_max, height[left]);
            suf_max = max(suf_max, height[right]);
            ans += pre_max < suf_max ? pre_max - height[left++] : suf_max - height[right--];
        }
        return ans;
    }
};

3️⃣ 单调栈

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++) {
            while (!st.empty() && height[i] >= height[st.top()]) {
                int bottom_h = height[st.top()];
                st.pop();
                if (st.empty()) {
                    break;
                }
                int left = st.top();
                int dh = min(height[left], height[i]) - bottom_h; // 面积的高
                ans += dh * (i - left - 1);
            }
            st.push(i);
        }
        return ans;
    }
};

407. 接雨水 II （短板效应）

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

示例 1:

img

1
2
3
输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。

示例 2:

img

1
2
输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

1️⃣ 优先队列 priority_queue 维护短板

哪个格子的接水量，在一开始就能确定？

  • 最外面一圈的格子是无法接水的。
  • 假设 (0,1) 的高度是最外面一圈的格子中最小的，且高度等于 5，那么和它相邻的 (1,1)，我们能知道：
    • (1,1) 的水位不能超过 5，否则水会从 (0,1) 流出去。
    • (1,1) 的水位一定可以等于 5，这是因为 (0,1) 的高度是最外面一圈的格子中最小的，(1,1) 的水不可能从其他地方流出去。

我们从最外面一圈的格子开始。想象成一个木桶，最外面一圈格子的高度视作木板的高度。

接着上面的讨论：

  • 如果 (1,1) 的高度 ≥5，那么 (0,1) 这块木板就没用了，我们去掉 (0,1) 这块木板，改用 (1,1) 这块木板。
  • 如果 (1,1) 的高度 <5，假设我们接的不是水，是水泥。那么把 (1,1) 的高度填充为 5，仍然可以去掉 (0,1) 这块木板，改用 (1,1) 这块（填充水泥后）高为 5 的木板水泥板。

继续，从当前木板中，找到一根最短的木板。假设 (1,1) 是当前所有木板中最短的，那么其邻居 (1,2) 和 (2,1) 的水位就是 (1,1) 的高度，因为超过 (1,1) 高度的水会流出去。然后，去掉 (1,1) 这块木板，改用 (1,2) 和 (2,1) 这两块木板。依此类推。

由于每次都要找最短的木板，所以用一个最小堆维护木板的高度。按照上述做法，不断循环，直到堆为空。

为方便实现，代码在初始化堆的时候，直接遍历了整个矩阵。

「42. 接雨水 」那题需要维护左右两个指针，本题相当于维护了“一圈”指针。42 那题每次取左右最小的指针，然后移动到相邻位置上；本题也是取最小的指针（出堆），往周围的邻居移动（入堆）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    pq.push({heightMap[i][j], i, j});
                    heightMap[i][j] = -1;
                }
            }
        }
        int ans = 0;
        while (!pq.empty()) {
            auto [min_height, i, j] = pq.top();
            pq.pop();
            for (auto& [dx, dy] : DIRS) {
                int x = i + dx;
                int y = j + dy;
                if (x >= 0 && y >= 0 && x < m && y < n && heightMap[x][y] != -1) {
                    ans += max(min_height - heightMap[x][y], 0);
                    pq.push({max(min_height, heightMap[x][y]), x, y});
                    heightMap[x][y] = -1;
                }
            }
        }
        return ans;
    }
};

907. 子数组的最小值之和

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：

1
2
3
4
5
输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

1️⃣ 单调栈

解法等价于「84. 柱状图中最大的矩形」，本题计算以 arr[i] 为最小值的子数组的个数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    const int MOD = 1e9 + 7;

public:
    // 类似题目: 84. 柱状图中最大的矩形
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        // 左边界 left[i] 为左侧严格小于 arr[i] 的最近元素位置（不存在时为 -1）
        vector<int> left(n, -1);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && arr[st.top()] >= arr[i])
                st.pop();
            if (!st.empty())
                left[i] = st.top();
            st.push(i);
        }

        st = stack<int>();
        // 右侧找 <= 是为了避免重复统计
        // 右边界 right[i] 为右侧小于等于 arr[i] 的最近元素位置（不存在时为 n）
        vector<int> right(n, n);
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && arr[st.top()] > arr[i])
                st.pop();
            if (!st.empty())
                right[i] = st.top();
            st.push(i);
        }
        long ans = 0l;
        for (int i = 0; i < n; i++) {
            ans += (long)arr[i] * (i - left[i]) * (right[i] - i);
        }
        return ans % MOD;
    }
};

1793. 好子数组的最大分数

给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

示例 1：

1
2
3
输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

1️⃣ 背向双指针

我们尝试从 $i=k, j=k$ 出发，通过不断移动指针来找到最大矩形。比较 nums[i−1] 和 nums[j+1] 的大小，谁大就移动谁（一样大移动哪个都可以）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int max_score = nums[k], n = nums.size(), mn = nums[k];
        int l = k, r = k;
        for (int t = 1; t < n; t++) {
            if (r == n - 1 || (l && nums[l - 1] > nums[r + 1])) {
                mn = min(mn, nums[--l]);
            } else {
                mn = min(mn, nums[++r]);
            }
            max_score = max(max_score, mn * (r - l + 1));
        }
        return max_score;
    }
};

2️⃣ 单调栈

本题要计算的分数，和「84. 柱状图中最大的矩形 」是一样的，计算的是最大矩形面积，**只不过多了一个约束：矩形必须包含下标 k**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> left(n), right(n);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[st.top()] >= nums[i]) {
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        st = stack<int>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && nums[st.top()] >= nums[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 分数的定义其实就是矩形面积: 同「84. 柱状图中最大的矩形」
            int score = nums[i] * (right[i] - left[i] - 1);
            // 仅仅加一个判断条件即可
            if (left[i] < k && right[i] > k)
                ans = max(ans, score);
        }
        return ans;
    }
};
许可协议

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

分享文章
✍️ Yikun Wu 已发表了 69 篇文章 · 总计 293k 字，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处

🌀 本站总访问量 次