代码随想录算法训练营day49（0217）

单调栈的收尾，接雨水很常考

1.接雨水

题目

42. 接雨水

给定 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.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

`代码（三种方法）`

1.暴力解法

计算雨水面积有横向跟纵向两种，个人认为纵向更容易理解。

那其实就是当前雨水左边跟右边的最大里面挑个最小的作为长，宽就是1。

代码随想录，看这个很好理解，但是暴力无法做到全部通过，所以还要优化。

class Solution {
public:int trap(vector<int>& height) {int sum=0;for(int i=0;i<height.size();i++){if(i==0||i==height.size()-1) continue;int lheight=height[i];int rheight=height[i];for(int r=i+1;r<height.size();r++){if(height[r]>rheight){rheight=height[r];}}for(int l=i-1;l>=0;l--){if(height[l]>lheight){lheight=height[l];}}int h=min(lheight,rheight)-height[i];if(h>0) sum+=h;}return sum;}
};

2.双指针

超时的原因就是里面那层for循环，那如果解决寻找当前节点左右两边柱子的最大高度，就可以解决这个问题了。双指针法其实就是将每个当前柱子左右两边的最大高度提前写入数组里，降低时间复杂度。

class Solution {
public:int trap(vector<int>& height) {vector<int>maxLeft(height.size(),0);vector<int>maxRight(height.size(),0);//每个柱子左边最大高度maxLeft[0]=height[0];for(int i=1;i<height.size();i++){maxLeft[i]=max(height[i],maxLeft[i-1]);}//每个柱子右边最大高度maxRight[height.size()-1]=height[height.size()-1];for(int i=height.size()-2;i>=0;i--){maxRight[i]=max(height[i],maxRight[i+1]);}int sum=0;for(int i=0;i<height.size();i++){int count=min(maxLeft[i],maxRight[i])-height[i];sum+=count;}return sum;}
};

3.单调栈

其实思路也是比较明确的，就是看敢不敢往这里想

class Solution {
public:int trap(vector<int>& height) {stack<int>st;st.push(0);int sum=0;for(int i=1;i<height.size();i++){//第一种if(height[i]<height[st.top()]){st.push(i);}//第二种else if(height[i]==height[st.top()]){st.pop();st.push(i);}//第三种else{while(!st.empty()&&height[i]>height[st.top()]){int mid=st.top();st.pop();if(!st.empty()){int h=min(height[st.top()],height[i])-height[mid];int w=i-st.top()-1;sum+=h*w;}}st.push(i);}}return sum;}
};

2.柱状图中最大的矩形

跟接雨水差不多，也是给了三种方法

题目

84. 柱状图中最大的矩形

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

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

示例 1:

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

示例 2：

输入： heights = [2,4]
输出： 4

代码（三种方法）

1.暴力方法

依旧是超时，但是可以作为一种思路，只是有部分用例过不了

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int sum=0;for(int i=0;i<heights.size();i++){int left=i;int right=i;for(;left>=0;left--){if(heights[i]>heights[left]) break;}for(;right<heights.size();right++){if(heights[i]>heights[right]) break;}int w=right-left-1;int h=heights[i];sum=max(sum,w*h);}return sum;}
};

2.双指针

写出来了，但是对于左右数组那里其实不太明白，算是糊糊涂涂过得

class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> maxLeftIndex(heights.size());vector<int> maxRightIndex(heights.size());int size = heights.size();// 记录每个柱子，左边第一个小于该柱子的下标maxLeftIndex[0]=-1;for (int i = 1; i < size; i++) {int t = i - 1;while (t >= 0 && heights[t] >= heights[i]) { //这里不太懂t = maxLeftIndex[t];}maxLeftIndex[i]=t;}maxRightIndex[size-1]=size;for(int i=size-2;i>=0;i--){int t=i+1;while(t<size&&heights[t]>=heights[i]){t=maxRightIndex[t];}maxRightIndex[i]=t;}int result=0;for(int i=0;i<size;i++){int sum=heights[i]*(maxRightIndex[i]-maxLeftIndex[i]-1);result=max(result,sum);}return result;}
};

3.单调栈

敲不下去了，原理其实不难，就是开始跟结尾要加0，然后单调栈顺序是从大到小的！！

// 版本一
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈，从下标1开始for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) { // 情况一st.push(i);} else if (heights[i] == heights[st.top()]) { // 情况二st.pop(); // 这个可以加，可以不加，效果一样，思路不同st.push(i);} else { // 情况三while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是whileint mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};