Leetcode刷题java之42. 接雨水（一天一道编程题之四十三天）

布满荆棘的人生 2023-07-21 05:40 37阅读 0赞

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了99.96% 的用户

内存消耗 :39.6 MB, 在所有 Java 提交中击败了11.87%的用户

题目：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: \[0,1,0,2,1,0,1,3,2,1,2,1\]  
输出: 6

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/trapping-rain-water  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

参考：[https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/][https_leetcode-cn.com_problems_trapping-rain-water_solution_xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8]

计算当前列的时候，找到左边的最大值和右边的最大值，选择他们之中小的，如果这个小的大于当前值，那么就加上这个差。

然后发现最大的左和最大的右每次都计算一次，还不如用一个数组存起来，进行了一次优化。

然后我从左边进行遍历的时候可以正好把左边的更新，又进行了一次优化。

那么我要是从两边遍历，双指针岂不是又可以优化一次？

代码：（双指针）

class Solution {
        public int trap(int[] height) {
            int sum=0;
            int max_left=0;
            int max_right=0;
            int left=1;
            int right=height.length-2;
            while(left<=right)
            {
                if(height[left-1]<height[right+1])
                {
                    max_left=Math.max(max_left,height[left-1]);
                    //此时max_left就是小的了，因为上面的if已经判断过了
                    if(max_left>height[left])
                    {
                        sum=sum+max_left-height[left];
                    }
                    left++;
                }else
                {
                    max_right=Math.max(max_right,height[right+1]);
                    if(max_right>height[right])
                    {
                        sum=sum+max_right-height[right];
                    }
                    right--;
                }
            }
            return sum;
        }
    }

[https_leetcode-cn.com_problems_trapping-rain-water_solution_xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8]: https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/