42. 接雨水

题目:https://leetcode-cn.com/problems/trapping-rain-water/

代码:

class Solution {

    public int trap(int[] height) {
        int sum = 0;
        int left = getFirstLeft(height);
        int right;
        
        while (left < height.length-1) {
            right = getRight(height, left);
            //统计杯子中的水量
            sum = sum + (right - left-1) * Math.min(height[left], height[right]);
            //去掉杯底非水的部分
            for (int i = left + 1; i < right; i++) {
                sum = sum - height[i];
            }
            //找下一个杯子,此时新杯子的左杯壁为当前杯子的右杯壁
            left = right; 
        }
        return sum;
    }

    /**
     * 获取第一个左杯壁的位置
     * @param height
     * @return
     */
    private int getFirstLeft(int[] height){
        for (int i = 0; i < height.length; i++) {
            if (height[i] >0) {
                //只要有高度,就算
                return i;
            }
        }
        return height.length;
    }

    /**
     * 获取右杯壁的位置
     * @param height
     * @param left
     * @return
     */
    private int getRight(int[] height, int left) {
        //默认右杯壁位置为整个数组的最右边
        int right = height.length-1;
        for (int i = left+1; i < height.length; i++) {
            //从左杯壁+1位置开始找
            if (height[i] >= height[left]) {
                //第一个高度大于等于左杯壁的就是右杯壁
                return i;
            } else if (height[i] > height[right]) {
                //如果上述条件找不到,即当前左杯壁已经是最高,则寻找右边元素中最高的值做右杯壁
                right = i;
            }
        }
        return right;
    }

}

因为数组是int类型,所以高度都是整数。一开始我的方案是将1个高度想象成1块砖头,设定一个水平线h,h=0,然后遍历数组,只要数组中的值小于h就代表本层这个位置是有水的,则水量+1,遍历结束之后水平线h自增1继续重复遍历直到水平线大于数组中最高的元素。简单来说思想就是一层一层的去计算水量,在数据量比较小的情况下,结果还是准确的,数据量一大耗时就太长了,而且我是真的没有想到最后一个测试用例的输入数据有一万多个数。直接导致超时没有ac,没办法,换方案呗。


新方案的思路如图:遍历数组,将数组划分成一个个装水的杯子,如图中红线所示。

对于杯子来说(二维空间条件下)一个杯子可以分成:左杯壁,右杯壁,杯底。而杯子中的水量=最矮杯壁*杯底宽度-杯底厚度

仔细观察图,题目欲求的水量我们可以根据上述条件,转化成一个个杯子,通过计算每个杯子的水量之和即可得出答案。根据杯子水量的计算公式,我们需要知道每个杯子的左杯壁,右杯壁,杯底的宽度和厚度这四个变量。

左杯壁:从0位置开始,第一个有高度的值就可以作为左杯壁,而下一个杯子的左杯壁就是当前杯子的右杯壁。

右杯壁:从左杯壁的位置开始往右找,第一个大于左杯壁的值就是右杯壁,如果剩下的数据都没有比左杯壁还高,那么剩下的数据中最大的一个就是右杯壁。

杯底宽度:右杯壁-左杯壁-1

杯底厚度:遍历左杯壁到右杯壁的值,依次减去他们即可。

综上只需要将其转化成代码即可,具体的参考代码。值得骄傲的是,本方案还不错,打败了99.99%的用户。


支付宝搜索:344355 领取随机红包

如果文章对您有帮助的话,欢迎老板打赏↑↑↑(请我吃饭😋