代码随想录算法训练营
Day49 代码随想录算法训练营第 49 天 |LeetCode42 接雨水 LeetCode84 柱状图中最大面积矩形
目录
前言
LeetCode42 接雨水
LeetCode84 柱状图中最大面积矩形
一、LeetCode42 接雨水
1.题目链接
2.思路
（1）寻找元素height[i]前后第一个大于它的元素，左边第一个大于height[i]的元素记作height[left] ，右边第一个大于height[i]的元素记作height[right]，[left+1,right-1]区间内，height[i]为最大高度
和原来的相比，增加了[left+1,right-1]区间内,最小高度差的雨水，即
(min(height[right],height[left])-height[mid])*(right-left-1)
（2）单调栈
1）下标0入
2）height[i]小于等于栈顶元素，入栈
3）循环：栈不空，且height[i]小于栈顶元素
- 栈顶下标记作mid（因为栈顶元素在中间）
- 弹出
- 如果空：mid左边没有比他大的，所以跳过
- 如果不空：
- 现在的栈顶，原本的栈顶之下第一个元素是左边第一个大于height[mid]的元素
- 当前增加了[s.top()+1,i-1]区间内,最小高度差的雨水
res +=（min(height[s.top()], height[i]) - height[mid]）*（i - s.top() - 1）
3.题解
class Solution {
public:
stack<int> s;
int trap(vector<int>& height) {
int res = 0;
s.push(0);
int n = height.size();
for (int i = 1; i < n; i++) {
if (height[s.top()] > height[i]) {
s.push(i);
} else if(height[s.top()] ==height[i])
{
s.pop();
s.push(i);
}
else {
while (!s.empty() && height[s.top()] < height[i]) {
int mid = s.top();
s.pop();
if (!s.empty()) {
int h = min(height[s.top()], height[i]) - height[mid];
int w = i - s.top() - 1;
res += w * h;
}
}
s.push(i);
}
}
return res;
}
};
二、LeetCode84 柱状图中最大面积矩形
1.题目链接
2.思路
（1）寻找元素height[i]前后第一个小于它的元素，左边第一个小于height[i]的元素记作height[left] ，右边第一个小于height[i]的元素记作height[right]
[left+1,right-1]区间内，height[i]为最大高度
当前矩形面积为[left+1,right-1]区间内，高为height[i]的矩形面积
（2）单调栈
1）下标0入
2）height[i]大于等于栈顶元素，入栈
3）循环：栈不空，且height[i]小于栈顶元素
- 栈顶下标记作mid（因为栈顶元素在中间）
- 弹出
- 如果空：当前矩形面积为[mid,i-1]区间内，高为height[mid]的矩形面积
当次结果为（i-mid)*height[mid] - 如果不空：
- 现在的栈顶，原本的栈顶之下第一个元素是左边第一个小于height[mid]的元素
- 当前矩形面积为[s.top()+1,i-1]区间内，高为height[mid]的矩形面积
当次结果为（i-s.top()-1)*height[mid]
3.题解
class Solution {
public:
stack<int> s;
int largestRectangleArea(vector<int>& heights) {
int res = 0;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
int n = heights.size();
s.push(0);
for (int i = 1; i < n; i++) {
if (heights[s.top()] <= heights[i]) {
s.push(i);
} else {
while (!s.empty() && heights[s.top()] > heights[i]) {
int mid = s.top();
s.pop();
if (s.empty()) {
res = max(res, heights[mid] * (i - mid));
} else {
res = max(res, heights[mid] * (i - s.top() - 1));
}
}
s.push(i);
}
}
return res;
}
};
总结
单调栈用于解决寻找元素左右第一个大于或小于它的元素位置的问题
单调栈里面存放的元素都是待处理的元素