42. 接雨水

张伦聪zhangluncong

发布于 2022-10-26 18:03:26

1820

发布于 2022-10-26 18:03:26

文章被收录于专栏：张伦聪的技术博客

给定 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

解：很抽象，双指针，主要是要理解为什么左边最大值大于右边最大值时候，右指针要往左移动，而不是左指针继续往右移动。也可以这样做：先循环找出整个数组最大值，分成两边，分别向这个最大值遍历。

public int trap(int[] height) {
        int res = 0;
        if (height == null || 0 == height.length) {
            return res;
        }
        int len = height.length;
        int l = 0;
        int r = len - 1;
        int lmax = 0;
        int rmax = 0;
        while (l < r) {
            lmax = Math.max(lmax, height[l]);
            rmax = Math.max(rmax, height[r]);
            if (lmax > rmax) {
                res += rmax - height[r];
                r--;
            } else {
                res += lmax - height[l];
                l++;
            }
        }
        return res;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-07-12，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历