代码随想录算法训练营第五十三天 | 42. 接雨水，84.柱状图中最大的矩形
五十三天打卡，今天解决单调栈的最后两题
42.接雨水
题目链接
解题过程
- 没想到怎么做，用双指针思路更直接
- 当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。
- 为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。用空间换时间
- 当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。
双指针法
class Solution {
public:int trap(vector<int>& height) {int len = height.size();if (len <= 2) return 0;vector<int>maxLeft(len);vector<int>maxRight(len);maxLeft[0] = height[0];for (int i = 1; i < len; i++) {maxLeft[i] = max(maxLeft[i - 1], height[i]);}maxRight[len - 1] = height[len - 1];for (int i = len - 2; i >= 0; i--) {maxRight[i] = max(maxRight[i + 1], height[i]);}int result = 0;for (int i = 0; i < len; i++) {int count = min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) result += count;}return result;}
};
单调栈
class Solution {
public:int trap(vector<int>& height) {if (height.size() <= 2) return 0;stack<int>st;st.push(0);int sum = 0;for (int i = 1; i < height.size(); i++) {while (!st.empty() && height[i] > height[st.top()]) {int mid = st.top();st.pop();if (!st.empty())sum += (min(height[st.top()], height[i]) - height[mid]) * (i - st.top() - 1);}st.push(i);}return sum;}
};
84.柱状图中最大的矩形
题目链接
解题过程
- 本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序
- 栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
- 开头和结尾都要加元素0，应对数组元素单调递增或递减
单调栈
class Solution {
public:int largestRectangleArea(vector<int>& heights) {heights.insert(heights.begin(), 0);heights.push_back(0);stack<int>st;st.push(0);int result = 0;for (int i = 1; i < heights.size(); i++) {while (!st.empty() && heights[i] < heights[st.top()]) {int mid = st.top();st.pop();if (!st.empty()) {result = max(result, heights[mid] * (i - st.top() - 1));}}st.push(i);}return result;}
};