leetcode接雨水问题

1.给定n个非负整数a1，a2，…，an，其中每个表示坐标（i，ai）处的点。绘制n条垂直线，使得线i的两个端点位于（i，ai）和（i，0）。找到两条线，它们与x轴一起形成一个容器，这样容器就含有最多的水。

注意：您不会倾斜容器，n至少为2。
leetcode接雨水问题
上面的垂直线由数组[1,8,6,2,5,4,8,3,7]表示。在这种情况下，容器可容纳的最大水面积（蓝色部分）为49。

有没有和我一样傻的，第一次看题的时候都不知道啥意思。傻到不知道横坐标是啥，其实横坐标就是数组的索引，纵坐标就是数组值。找到与x轴围成的面积最大就行了。
思路：双指针，从两边开始，较低的一边指针移动，上一次的宽度已经比你下一次大了，只有，高度超过上一次才有可能有更大的面积。

代码如下：

class Solution {
    public int maxArea(int[] height) {
       int i = 0,j = height.length -1;
       int max = 0;
        while(i<j){
            max = Math.max(max,Math.min(height[i],height[j])*(j-i));
            if(height[i]<height[j]){
                i++;
            }else {
            j--;    
            }
        }
        return max;
    }
}

2.给定n个非负整数表示每个柱的宽度为1的高程图，计算下雨后能够捕获的水量。
leetcode接雨水问题
上面的高程图由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示。在这种情况下，6个单位的雨水（蓝色部分）被困住。

双指针法，较低的一方移动，这样保证，另一侧起码有比你高的。
最好自己跟着代码手动跑一遍就理解了。

class Solution {
    public int trap(int[] height) {
        int a = 0;
        int b = height.length-1;
        int leftMax = 0;
        int rightMax = 0;
        int max = 0;
        while(a<b){
            leftMax = Math.max(height[a],leftMax);
            rightMax = Math.max(height[b],rightMax);
            if(leftMax<rightMax){
                max+=(leftMax-height[a]);
                a++;
            }else{
                max+=(rightMax-height[b]);
                b--;
            }
        }
        return max;
    }
}

leetcode接雨水问题

相关推荐