摘要

• 通过取模运算来模拟在数组中循环搜索元素，这比在数组后拼接一个相同数组更方便，空间复杂度更低。

• “接雨水”和“柱状图中的最大矩形”，都可以看成是对每个柱子，找一组 3 个柱子。不同的是“接雨水”是中间柱子比左右两边柱子矮，“柱状图中的最大矩形”是中间柱子比左右两边柱子高。

• 找一个元素左边和右边第一个更大的元素，用元素从栈顶向栈底递增的单调栈；找一个元素左边和右边第一个更小的元素，用元素从栈顶向栈底递减的单调栈。

LeetCode503 下一个更大元素II

503. 下一个更大元素 II - 力扣（Leetcode）

• 这道题目和代码随想录算法训练营打卡Day58中的题目的核心思路也是一样的，都是用单调栈来找任意元素的下一个更大元素。本题要额外做的只是控制如何在数组中循环搜索元素。

• 循环搜索需要以每个元素为起点，每个元素为终点（左开右闭）来搜索元素。可以在nums后再拼接一个nums得到一个nums1，遍历一次nums1就等价于循环遍历一次nums。

通过拼接数组来模拟循环遍历的题解代码如下

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> nums1(nums.begin(), nums.end());
        nums1.insert(nums1.end(), nums.begin(), nums.end());
        stack<int> st;
        vector<int> res(nums.size(), -1);

        for (int i = 0; i < nums1.size(); i++) {
            while (!st.empty() && nums1[i] > nums1[st.top()]) {
                res[st.top()] = nums1[i];
                st.pop();
            }
            st.push(i % nums.size());
        }
        
        return res;
    }
};

• 实际上，通过取模运算就可以实现循环遍历一次nums（即使是上面那种拼接数组的方法也用到了取模运算）。

使用取模运算来模拟循环遍历一次nums的题解代码如下

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> st;
        vector<int> res(nums.size(), -1);
        
        // i < 2 * nums.size()，对应在nums后再拼接一个nums
        for (int i = 0; i < 2 * nums.size(); i++) {
            int cur = i;// 保存当前的i
            i %= nums.size();// 取模得到nums中的下标

            while (!st.empty() && nums[i] > nums[st.top()]) {
                res[st.top()] = nums[i];
                st.pop();
            }
            st.push(i);
            
            i = cur;// 还原i
        }
        
        return res;
    }
};

LeetCode42 接雨水

42. 接雨水 - 力扣（Leetcode）

关于接雨水的简单分析

• 首先来看如何能接住雨水。对于一个柱子i，只有左边有比i更高的柱子并且右边也有比i更高的柱子时才能接住雨水。

• 接住雨水的高度是和左边第一个和右边第一个比i更高的柱子的高度有关的。就像木桶效应，三个柱子能形成的凹槽能接住的雨水的高度应该取决于左边第一个和右边第一个比i更高的柱子的较低的高度。

• 凹槽不一定是规则的，即不一定是规则的矩形，如何将凹槽分解成多个矩形来计算呢？
  • 按上面的分析，可以认为一个能接住雨水的矩形凹槽由三个柱子组成：
    • 左边较高的柱子，中间较低的柱子，右边较高的柱子。

• 那么，上面的这个不规则的凹槽，可以分解为：
  • [i-1, i, i+1]形成一个矩形凹槽
  • [i-1, i+1, i+2]形成一个矩形凹槽，为了避免重复计算，计算i+1为中间较低的柱子形成的凹槽时，可以看成从左边第一个较高的柱子i-1到中间柱子i+1间隔的其他柱子的高度都是i+1的高度，从右边第一较高的柱子i+2到中间柱子i+1的间隔的其他柱子也是同理。

使用单调栈的思想

1. 分解凹槽

   • 按以上分析，对于每一个柱子，都要找它右边第一个比它更高的柱子；除了找右边第一个比它更高的柱子之外，还要找左边第一个比它更高的柱子。由左边较高的柱子，中间较低的柱子，右边较高的柱子，三个柱子组成一个能接住雨水的凹槽。

   • 按以上分析来将不规则的凹槽分解成多个矩形，实际上是按照行来计算雨水的。

2. 找右边第一个更高的柱子，应该用递增栈，即柱子高度从栈顶到栈底递增

   • 那怎么找左边第一个更高的柱子呢？左边的柱子是遍历过的，应该被保存在栈中，并且柱子高度从栈顶到栈底递增，左边的先入栈，应该从栈顶往栈底开始找。
   • 栈顶的柱子st.top()作为中间较低的柱子时，左边第一个比st.top()更高的柱子就保存在栈中。将栈顶的柱子弹出并保存在变量mid中，然后栈顶的柱子就要找的是左边较高的柱子。

3. 找到了一组组成矩形凹槽的三个柱子，怎么计算能接住多少雨水？

   • 首先，雨水的高度应该等于左边较高的柱子和右边较高的柱子中最小的高度，并减去中间较低的柱子的高度，
   • 然后，三个柱子不一定能紧挨在一起，所以雨水的宽度也是要求的，按以上的分解规则，雨水的宽度

4. 如何使用单调栈

   • 从左到右遍历height

   • 栈为空，height[i]直接入栈

   • height[i] <= height[st.top()]，此时还没有“右边较高的柱子”，所以height[i]入栈

   • height[i] > height[st.top()]，此时已经出现了“右边较高的柱子”，栈顶的柱子作为中间较低的柱子。要取“左边较高的柱子”，就要将栈顶的柱子弹出，栈顶的柱子保存在mid中，再尝试取栈顶的柱子作为“左边较高的柱子”。如果栈为空，说明没有”左边较高的柱子“，不能接住雨水。

   • height[i]作为”右边较高的柱子“的同时，也可以作为下一组的”左边较高的柱子“或者”中间较低的柱子“，所以不要忘记将height[i]入栈。

题解代码如下

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int res = 0;

        for (int i = 0; i < height.size(); i++) {
            while (!st.empty() && height[i] > height[st.top()]) {
                int mid = st.top();
                st.pop();
                if (st.empty()) break;
                int h = min(height[st.top()], height[i]) - height[mid];
                int w = i - st.top() - 1;
                res += h * w;
            }
            st.push(i);
        }

        return res;
    }
};

LeetCode84 柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（Leetcode）

• 这道题目和“接雨水”有异曲同工之妙，不同的是“接雨水”使用的是从栈顶到栈底递增的单调栈，而本题使用的是从栈顶到栈底递减的单调栈。

以一个柱子的高度为基准勾勒的最大矩形

• 三个柱子为一组
  • 中间较高的柱子，以这个柱子的高度作为矩形的高度，能勾勒出的最大矩形的宽度取决于左边第一个比中间柱子矮的柱子，和右边第一个比中间柱子矮的柱子。
  • 因为比中间柱子矮的柱子不能被包含在高度和中间柱子相等的矩形内，左边第一个比中间矮的柱子，和右边第一个比中间柱子矮的柱子，就决定了高度中间较高的柱子相等的矩形的宽度。
• 应该对每一个柱子i都求一次以height[i]为高度的最大矩形，那如果一个柱子左边或者右边没有比它矮的柱子怎么办？例如上图左边的高度为2的柱子和右边的高度为2的柱子，其左边（或右边）就没有更矮的柱子。但使用单调栈时，肯定是在第一次出现右边更矮的柱子计算栈顶的柱子能扩展出的最大矩形的面积，如果不处理左边或右边没有更矮的柱子的情况，就会丢失这个答案。

• 左边或右边没有更矮的柱子，其实也可以看成左边或右边有一个高度为0的柱子，这样才能对每一个柱子作为中间的柱子时，找到左边第一个更矮的柱子和右边第一个更矮的柱子。以0为高度的矩形面积就是0，所以在数组头部和数组尾部添加的0不需要按“三个柱子为一组”的规则计算矩形面积。

使用单调栈来寻找每一组“3个柱子”

• 3 个柱子为一组，就能计算出中间较高的柱子能扩展出的最大矩形面积
  • 中间较高的柱子，矩形的高就是它的高
  • 左边较矮的柱子
  • 右边较矮的柱子
• 要找右边第一个比中间柱子矮的柱子，应该使用元素从栈顶到栈底递减的单调栈。
  • 从左到右遍历height
  • 栈为空，height[i]直接入栈
  • height[i] <= height[st.top()]，此时还没有“右边较矮的柱子”，所以height[i]入栈
  • height[i] > height[st.top()]，此时已经出现了“右边较矮的柱子”，栈顶的柱子作为中间较高的柱子。要取“左边较矮的柱子”，就要将栈顶的柱子弹出，栈顶的柱子保存在mid中，再尝试取栈顶的柱子作为“左边较矮的柱子”。如果栈为空，只可能是0被弹出。
  • height[i]作为”右边较矮的柱子“的同时，也可以作为下一组的”左边较矮的柱子“或者”中间较高的柱子“，所以不要忘记将height[i]入栈。
• 矩形的高度为height[mid]，宽度为i - st.top() - 1

题解代码如下

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int res = 0;

        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int mid = st.top();
                st.pop();
                if (!st.empty()) {
                    int left = st.top();
                    int right = i;
                    int w = i - st.top() - 1;
                    int h = heights[mid];
                    res = max(res, w * h);
                }
                
            }
            st.push(i);
        }

        return res;
    }
};