题目描述

现有 n 个宽度为 1 的柱子，给出 n 个非负整数依次表示柱子的高度，排列后如下图所示，此时均匀从上空向下撒青豆，计算按此排列的柱子能接住多少青豆。（不考虑边角堆积）

题解

这道题是很典型的接雨水问题, 可以参考LeetCode, 这面说一下解题的思路:

动态规划

对于任意柱子, 其可以接住的青豆数受自身高度以及左右两边各自最高柱子的影响, 算式表达可以写为

Min(left.Max,right.Max)-height

对于这种情况, 我们只需判断出对应需要的各项参数, 进行运算即可获得正确答案

初始化两个数组left, right分别存入当前位置左边和右边最高柱的高度.

例如当输入为{5,0,2,1,4,0,1,0,3}时

left={5,5,5,5,5,5,5,5,5} right={5,4,4,4,4,3,3,3,3}

则下标为1的位置上可接住的青豆数为Min(left.Max,right.Max)-height = Min(5,4)-0 = 4

具体代码如下:

public static int trap(int[] height) {
    int[] left = new int[height.length];
    int max = -1;
    for (int i = 0; i < height.length; i++) {
        if (height[i] > max) max = height[i];
        left[i] = max;
    }
    max = -1;
    int sum = 0;
    for (int i = height.length - 1; i >= 0; i--) {
        if (height[i] > max) max = height[i];
        if (left[i] > max) sum += max - height[i];
        else sum += left[i] - height[i];
    }
    return sum;
}

这种解法的时间复杂度为O(n), 空间复杂度为O(n)

码上掘金代码片段

双指针

双指针解法是在动态规划基础上对于空间复杂度的优化, 根据计算方式

Min(left.Max,right.Max)-height

我们可以认为影响当前列青豆数的是左右两边最大值较小的一方, 那我们可以定义分别指向最左侧和最右侧的指针, 通过移动指针来计算当前列青豆数, 以此优化空间复杂度

首先比较左右指针指向的大小, 根据Min(left.Max,right.Max)可知较小的会影响当前列的青豆数, 同时因为比较的双方要求为left.Max和right.Max, 所以在移动过程中需要更新对应的值

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1;
    int right = height.length - 2;
    for (int i = 1; i < height.length - 1; i++) {
        if (height[left - 1] < height[right + 1]) {
            max_left = Math.max(max_left, height[left - 1]);
            int min = max_left;
            if (min > height[left]) {
                sum = sum + (min - height[left]);
            }
            left++;
        } else {
            max_right = Math.max(max_right, height[right + 1]);
            int min = max_right;
            if (min > height[right]) {
                sum = sum + (min - height[right]);
            }
            right--;
        }
    }
    return sum;
}

这种解法的时间复杂度为O(n), 空间复杂度为O(1)

小结

其他解题思路还包括单调栈, 接雨水是面试笔试中常见的题目, 拥有多种变式, 需要多加了解和练习