Hot100 42接雨水

1. 题目描述

2.思路

2.1 求最大的前缀和后缀

        根据题目描述，雨水总和就是蓝色方块加起来的总和。怎么思路很简单，为了不让水溢出，那么两边只能取最短的一截。 根据当前柱子所处的位置，算出前面最高的和后面最高的柱子（因为水是流动的），这样求最小的柱子长度，就是当前桶能装最大水量，让然还要减去里面的柱子高度。那就需要额外的数组来存储最大前缀和最小前缀了。

        整体代码如下

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] pre_max = new int[len];
        int[] bef_max = new int[len];
        int result = 0;
        pre_max[0] = height[0];
        for (int i = 1; i < len ; i++) {
            pre_max[i] = Math.max(pre_max[i - 1], height[i]);
        }
        bef_max[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            bef_max[i] = Math.max(height[i], bef_max[i + 1]);
        }
        //遍历相减 = 当前容器存水量    然后计算总和
        for (int i = 0; i < len; i++) {
            int min = Math.min(pre_max[i], bef_max[i]);
            result += min - height[i];
        }
        return result;

    }

}

时间复杂度：O(n)

原文地址：https://blog.csdn.net/Wdc_12/article/details/143795129

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！