【代码随想录训练营第42期 Day49打卡 - 接雨水和柱状图最大矩形问题
目录
一、做题心得
二、题目与题解
题目一：42. 接雨水
题目链接
题解1：双指针
题解2：单调栈
题目二：84.柱状图中最大的矩形
题目链接
题解：单调栈
三、小结
一、做题心得
今天是单调栈问题的Part2，打卡的是接雨水问题和柱状图中最大的矩形。作为面试中极为常考的问题，个人感觉挺难理解的，尤其是使用单调栈这一思路。这一类型设计柱状图的题目，必须结合图像仔细判断，并考虑清楚当前柱子以及其左右边界，进而通过单调栈实现。
用于解决在一维数组中找第一个满足某种条件的数，我们选择使用单调栈。
二、题目与题解
题目一：42. 接雨水
题目链接
42. 接雨水 - 力扣（LeetCode）
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：
输入：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 个单位的雨水（蓝色部分表示雨水）。示例 2：
输入：height = [4,2,0,3,2,5] 输出：9提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
题解1：双指针
双指针的解法是按照列来计算：只需要计算并加上当前柱子这一列能接的雨水（宽恒为1）
使用两个指针left和right分别从数组的两端开始
维护两个变量leftMax和rightMax，分别表示左右指针指向的柱子左右两边的最大高度
移动较短的柱子对应的指针，并更新最大高度
如果leftMax < rightMax，则计算left指针指向柱子的接水量，并移动left指针
如果rightMax <= leftMax，则计算right指针指向柱子的接水量，并移动right指针
当left和right指针相遇时，停止计算
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0; //初始化接水的总量为0
int n = height.size();
//双指针：左右指针
int left = 0;
int right = n - 1;
int leftmax = height[left]; //左边界最大高度：初始化左边界的最大高度为第一个柱子的高度
int rightmax = height[right]; //右边界最大高度：初始化右边界的最大高度为最后一个柱子的高度
while (left < right) { //左右指针重合时，循环结束
leftmax = max(leftmax, height[left]); //更新左边界的最大高度
rightmax = max(rightmax, height[right]); //更新右边界的最大高度
if (leftmax < rightmax) { //左 < 右
ans += leftmax - height[left]; //当前柱子可以接水的量等于左边界的最大高度减去当前柱子的高度
left++; //左指针右移
}
else { //左 >= 右：同理
ans += rightmax - height[right];
right--;
}
}
return ans;
}
};题解2：单调栈
单调栈的解法按照行方向（横向）来计算雨水。
为什么使用单调栈？因为单调栈可以有效地找到每个柱子左右两边最近的更高的柱子。即：用于解决在一维数组中找第一个满足某种条件的数，我们选择使用单调栈。
两根柱子一样高怎么办？直接略过即可，因为不妨碍计算雨水的体积，使用最右边的柱子来计算宽度。
思路：
使用一个栈来维护一个单调递减的柱子高度序列
当遇到一个比栈顶元素高的柱子时，说明找到了一个凹槽，可以接水
计算凹槽的宽度和高度，并累加接水量
将当前柱子的高度加入栈中
重点需要理解的点：栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
代码如下：
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st; //单调栈：可以有效地找到每个柱子左右两边最近的更高的柱子 -- 两根柱子中间就是雨水
st.push(0); //先将下标0的柱子加入到栈中，作为初始边界 -- 确保第一个柱子有左边界
int ans = 0; //记录接水量
for (int i = 1; i < height.size(); i++) { //从下标1开始，遍历数组height中的每一个柱子
while (!st.empty() && height[i] > height[st.top()]) { //当栈不为空，并且当前柱子的高度大于栈顶柱子的高度
int mid = st.top(); //用mid记录原栈头元素 -- 中间的柱子，即凹槽底部的柱子
st.pop(); //栈头出栈
if (!st.empty()) {
int h = min(height[st.top()], height[i]) - height[mid]; //计算凹槽的高度，即左右边界中较小的一个减去中间柱子的高度
int w = i - st.top() - 1; //计算凹槽的宽度，即当前柱子与栈顶柱子之间的距离减1
ans += h * w; //将凹槽的面积 h * w（即能接住的水量）加到总和中
}
}
st.push(i); //将当前柱子的下标加入栈中
}
return ans;
}
};题目二：84.柱状图中最大的矩形
题目链接
84. 柱状图中最大的矩形 - 力扣（LeetCode）
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4] 输出： 4提示：
1 <= heights.length <=1050 <= heights[i] <= 104
题解：单调栈
这题的关键：需要在数组的头部和尾部各添加一个高度为0的柱子，这是为了确保所有原始柱子都能出栈并计算面积。
具体来说：
如果不添加头部的高度为0的柱子，那么第一个柱子可能永远不会出栈，因为它的左侧没有比它矮的柱子。这会导致第一个柱子无法参与矩形面积的计算；
如果不添加尾部的高度为0的柱子，那么栈中可能还剩余一些元素，这些元素将无法出栈，因为它们的右侧没有比它们矮的柱子。这会导致这些柱子无法参与矩形面积的计算。
然后就是注意如何得到矩形区域：如果当前柱子的高度小于栈顶柱子的高度，说明找到了一个矩形区域。
其余的思路和接雨水相似，这里直接看代码。
代码如下：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(), 0); //在数组头部加入元素0，确保开始时栈中有元素，且能处理第一个柱子
heights.push_back(0); //在数组尾部加入元素0，确保所有柱子都能出栈，并计算面积
int n = heights.size(); //获取更新后的数组长度
st.push(0); //初始化栈，先将下标0加入栈中
int ans = 0;
for (int i = 1; i < n; i++) {
while (heights[i] < heights[st.top()]) { //当前柱子的高度小于栈顶柱子的高度时，说明找到了一个可能的矩形区域
int mid = st.top(); //取出栈顶元素，即矩形区域的中间柱子索引
st.pop();
int w = i - st.top() - 1; //矩形的宽度
int h = heights[mid]; //计算矩形的高度，为中间柱子的高度
ans = max(ans, w * h); //更新
}
st.push(i); //不要忘
}
return ans;
}
};三、小结
单调栈这一类问题较难，但也并非没有套路可循。这两天的打卡梳理了运用单调栈解题的步骤，相信通过更多的练习足以加深对于单调栈思路的理解。
力扣评论区的一句话足以说明：
用于解决在一维数组中找第一个（最近）满足某种条件的数，我们选择使用单调栈。