【LeetCode-困难题】42. 接雨水

题目

题解一：暴力双重for循环（以行计算水量）

1.先找出最高的柱子有多高（max = 3）
2.然后第一个for为行数（1，2，3）
3.第二个for计算每一行的雨水量（关键在于去除前面的空白区域）利用标志位

boolean iscup = true; //标志位，若第一次就少于本次最高水位，则直接跳过，如果是因为处在1 0 1谷底的0就得算水量

4.最后将每一行计算完的雨水量sum总和

//方法一：以行计算水量int sum = 0;//最终总和int maxdepth = max(height);//1-3列for(int i = 1;i<=maxdepth;i++){int temp = 0;boolean iscup = true;  //标志位，若第一次就少于本次最高水位，则直接跳过，如果是因为处在1 0 1谷底的0就得算水量//遍历整个数组for(int j=0;j<height.length;j++){//如果小于当前水位，则不更新任何数据  要保证不开始计算水位  才算  if(height[j]<i&&iscup) {continue;}else if(height[j]<i&&!iscup){//根据标志位来判断要不要计算水量temp = temp + 1;} if(height[j]>=i){sum = sum + temp; //把每次累计的temp加到 sumtemp = 0;//计算完水量，重置tempiscup = false;//更新标志位}}}return sum;

参考链接：解法一：按行求

题解二：按列求

求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。
装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。

1. 第一个for循环列数（1,2,3,4,5,6,7,8…）
2. 第二三个for循环，分别求出当前列的左边有右边的最大柱子
3. 找出两端最矮的，然后减去当前列的柱子高度就是当前列的水量
   参考链接：解法二：按列求

     int sum = 0;//最后的水量//最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2for(int i=1; i< height.length-1 ; i++){//找出左边最高int  maxleft = 0;for(int j = i-1;j>=0;j--){   //由当前数往前找if(maxleft<height[j])  maxleft = height[j];}//找出右边最高int  maxright = 0;for(int s = i+1;s<height.length;s++){  //由当前数往后找if(maxright<height[s])  maxright = height[s];}//找出两端最矮的int min = Math.min(maxleft,maxright);if(min > height[i]){sum = sum + (min - height[i]);//核心就是让两端最小的柱子减去柱子，若大于0，差值就是当前列的水量}}return sum;

题解三：动态规划

与上面题解二对比，会发现，每次对一列去求左右最大的柱子时，都会循环一遍左右两边的元素，导致会有很多重复操作，

可以使用动态规划，直接求出每一列的左边或右边的最大柱子

核心：

  int sum = 0;int[] maxleft = new int[height.length]; //用于存放i位置的左边的最大柱子int[] maxright = new int[height.length];//用于存放i位置的右边的最大柱子//注意边界问题 原则第一个柱子靠左最长柱子默认为0  则i从1开始，结束位置为倒数第二个，看图好理解for(int i=1;i<height.length-1;i++){//它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。maxleft[i] = Math.max(maxleft[i-1],height[i-1]);}for(int j = height.length-2;j>=0;j-- ){//它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。maxright[j] = Math.max(maxright[j+1],height[j+1]);}for(int i = 1;i<height.length-1;i++){int min  = Math.min(maxleft[i],maxright[i]);if(min>height[i]) sum = sum +(min -height[i]);}return sum;

题解四：双指针

动态规划中，我们常常可以对空间复杂度进行进一步的优化。

例如这道题中，可以看到，max_left [ i ] 和 max_right [ i ] 数组中的元素我们其实只用一次，然后就再也不会用到了。所以我们可以不用数组，只用一个元素就行了。我们先改造下 max_left。

动态图解链接：图解接雨水双指针

参考链接：解法四：双指针

    int maxLeft = height[0]; int maxRight = height[height.length -1];int left = 1;int right = height.length -2;int sum = 0;for(int i = 1 ; i <height.length -1;i++){//    while (left <= right) {//从左开始if(height[left - 1] < height[right + 1]){maxLeft = Math.max(maxLeft,height[left]);if(maxLeft > height[left]){sum = sum + (maxLeft - height[left]);}left++;}else {//从右开始maxRight = Math.max(maxRight,height[right]);if(maxRight > height[right]) {sum = sum + (maxRight - height[right]);} right--;}}return sum;

题解五：栈

参考视频：单调栈，经典来袭！LeetCode:42.接雨水

参考链接：代码随想录-接雨水

  if(height.length<=2) return 0;int sum = 0;Stack<Integer> stack = new Stack<>();int current = 0;//先把第一个元素下标加入栈stack.push(0);for(int i=1;i<height.length;i++){//如果要入栈的元素小于栈顶元素，则一直入栈if(!stack.empty()&&(height[i] <= height[stack.peek()])) {stack.push(i);}//如果入栈的元素栈顶元素相等，可以直接入栈，也可以先把栈顶元素出栈，再让重复的元素进栈，只是重复元素入栈到时候计算面积等于0，不影响结果else{while(!stack.empty()&&height[i] > height[stack.peek()]){int mid = stack.pop();if(!stack.empty()){int h = Math.min(height[stack.peek()],height[i]) - height[mid];int w = i - stack.peek() - 1;sum = sum + (h*w);}}stack.push(i);}}return sum;