AlgoPressAppearance
0042-接雨水
https://leetcode.cn/problems/trapping-rain-water
给定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 * 10^4
0 <= height[i] <= 10^5
思路:动态规划
动态规划
- 对于每个位置能接到雨水的垂直高度，取决于这个位置左边的最大高度和右边的最大高度，取其小值减去柱子本身的高度
- 如果遍历到某个位置的时候，再往左右遍历，那么时间复杂度为O(n^2)
- 但是我们可以使用动态规划，记录 leftMax的值 leftMax[i] = max(leftMax[i-1,height[i])，同理可以记录右边的最大值 rightMax
- 这样遍历两次之后，第三次遍历，取 min(leftMax,rightMax) - height[i] 即为能接到的雨水值，时间复杂度O(n)
参考代码
csharp
public class Solution {
public int Trap(int[] height) {
int[] dpLeftMax = new int[height.Length];
dpLeftMax[0] = height[0];
int[] dpRightMax = new int[height.Length];
dpRightMax[height.Length-1] = height[height.Length-1];
int ans = 0;
for(int i=1;i<height.Length;i++){
dpLeftMax[i] = Math.Max(dpLeftMax[i-1],height[i]);
}
for(int i=height.Length-2;i>=0;i--){
dpRightMax[i] = Math.Max(dpRightMax[i+1],height[i]);
}
//计算雨水值
for(int i=1;i<height.Length-1;i++){
int result = Math.Min(dpLeftMax[i],dpRightMax[i]) - height[i];
if(result > 0){
ans+=result;
}
}
return ans;
}
}
思路2：单调栈
目的是找到两侧高的柱子中间蓄水，所以当我们遇到比左侧低的柱子，就说明可以蓄水，直到比左侧高的柱子，我们就可以计算储存的水量。 从左侧开始，如果栈为空，则添加索引到栈
遍历，如果发现比栈内柱子低，持续压栈，直到比它高或相等，我们可以取出元素计算水量。
计算方法是： 取出栈元素的索引 pre, 则 i-pre-1 表示区间，然后他们的高度是 min(height[i],height[pre]) 水量等于它们的乘积 (i-pre-1) * min(height[i],height[pre])
参考代码
csharp
//[0,1,0,2,1,0,1,3,2,1,2,1]
public class Solution {
public int Trap(int[] height) {
int ans = 0;
Stack<int> stack = new Stack<int>();
for(int i=0; i<height.Length; i++){
while(stack.Count > 0 && height[i] >= height[stack.Peek()]){
int pre = stack.Pop();
if(stack.Count == 0){
break;
}
int left = stack.Peek();
int curWidth = i - left - 1;
int curHeight = Math.Min(height[left],height[i]) - height[pre]);
ans += curHeight * curWidth;
}
stack.Push(i);
}
}
}
复习DP：2022-04-03
csharp
public class Solution {
public int Trap(int[] height) {
//动态规划
int n = height.Length;
int[] left = new int[n];
int[] right = new int[n];
//计算左边
int max = height[0];
for(int i=1; i<n; i++){
left[i] = max;
max = Math.Max(height[i],max);
}
//计算右边
max = height[n-1];
for(int i=n-2; i>=0; i--){
right[i] = max;
max = Math.Max(height[i],max);
}
//计算总值
int total = 0;
for(int i=0; i<n; i++){
//Console.WriteLine("i={0},left={1},right={2},height={3}",i,left[i],right[i],height[i]);
int h = Math.Min(left[i],right[i]);
if(h > height[i]){
total += h-height[i];
}
}
return total;
}
}
复习：单调栈：2022-04-04
csharp
public class Solution {
public int Trap(int[] height) {
//单调递减栈
int total = 0;
Stack<int> stack = new Stack<int>();
stack.Push(0);
for(int i = 1; i < height.Length; i++){
while(stack.Count > 0 && height[i] >= height[stack.Peek()]){
int index = stack.Pop();
// int left = index+1; //注意这里弹出的 index 是要计算的值，所以left不可能在他右边，思路就错了
// int h = Math.Min(height[index],height[i]);
// for(int j=left; j<i; j++){
// total += h-height[j];
// }
if(stack.Count ==0){
//说明紧接着的数字就大于前面的数，否则 stack.Count 不会为空的
break;
}
int left = stack.Peek(); //弹出当前最小的节点之后，栈顶的那个元素就是最左边界(他大于当前的高度)
int curWidth = i - left - 1; // 就算宽度
int curHeight = Math.Min(height[left],height[i]) - height[index]; //高度是两边柱子的取最小值，然后减去当前柱子的高度
total += curHeight * curWidth;
}
stack.Push(i);
//Console.WriteLine("{0} = {1},",i,total);
}
return total;
}
}
复习：动态规划简化双指针
csharp
public class Solution {
public int Trap(int[] height) {
int total = 0;
int leftMax = 0, rightMax = 0;
int left = 0, right = height.Length-1;
while(left < right){
leftMax = Math.Max(height[left],leftMax);
rightMax = Math.Max(height[right],rightMax);
if(leftMax < rightMax){ //左边挡板小于右边挡板
total += leftMax - height[left];
left++;
}
else{
total += rightMax - height[right];
right--;
}
}
return total;
}
}
复习：两边柱子
csharp
public class Solution {
public int Trap(int[] height) {
int n = height.Length;
//每个柱子能取得水的最大高度取决于左右的高度
int max = 0;
int[] leftMax = new int[n];
for(int i=0;i<n;i++){
leftMax[i] = max;
max = Math.Max(max,height[i]);
}
max = 0;
int[] rightMax = new int[n];
for(int j=n-1;j>=0;j--){
rightMax[j] = max;
max = Math.Max(max,height[j]);
}
//计算面积
int sum = 0;
for(int i=0; i<n; i++){
int h = Math.Min(leftMax[i],rightMax[i]);
if(h > height[i]){
sum += h - height[i];
}
}
return sum;
}
}
复习单调栈:20220515
csharp
public class Solution {
public int Trap(int[] height) {
Stack<int> stack = new Stack<int>();
stack.Push(0);
int sum = 0;
for(int i = 1; i<height.Length; i++){
while(stack.Count > 0 && height[i] > height[stack.Peek()]){
int index = stack.Pop();
if(stack.Count == 0){ //说明高的紧挨着前面的矮的，没有空挡计算面积
break;
}
int left = stack.Peek();
int w = i - left -1; //计算中间的宽度
int h = Math.Min(height[left],height[i]) - height[index];
int area = w * h;
sum += area;
}
stack.Push(i);
}
return sum;
}
}