「青训营 X 码上掘金」主题 4——攒青豆

当青训营遇上码上

主题介绍

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

以下为上图例子的解析：
输入：height = [5,0,2,1,4,0,1,0,3]  
输出：17  
解析：上面是由数组 [5,0,2,1,4,0,1,0,3] 表明的柱子高度，在这种情况下，能够接 17 个单位的青豆。

思路解析

依据题目能够得出，能接住多少青豆取决于凹槽两边柱子的高度，而且以矮的柱子为准。

方法一

该方法选用次序遍历的方法，也便是从左到右遍历或者从右到左遍历。

以题目为例，咱们能够从左向右遍历数组，来核算能接住多少青豆，遍历从数组下标1开端，由于假如0不是柱子的话也接不到豆子。

1. i = 1，该方位没有柱子(柱子高为0)，左边最大值为5，右侧最大值为4，所以1方位能够接到4颗青豆。
2. i = 2，该方位柱子高位2，左边最大值为5，右侧最大值为4，所以2方位能够接到4 - 2颗，即2颗青豆。
3. i = 3，该方位柱子高位1，左边最大值为5，右侧最大值为4，所以2方位能够接到4 - 1颗，即3颗青豆。
4. i = 4，该方位柱子高位4，左边最大值为5，右侧没有比4更大的值，所以4方位接不到豆子。
5. ……
6. 以此类推，遍历整个数组就能够得出整个数组能接到多少青豆了。

方法二

选用双指针法，从两端向中间遍历。

该方法思路如下：

1. 先界说两个变量来记录左右两端的最大值。
2. 从左右两端向中间遍历。
3. 假如左右指针指向的值大于对应的最大值，则更新最大值为当前值。
4. 否则，核算青豆数量。
5. 当左右两个指针为同一方位时，结束循环。

代码完成

代码完成选用方法二双指针方式，代码如下：

public class Main {
    public static void main(String[] args) {
        int[] height = { 5, 0, 2, 1, 4, 0, 1, 0, 3};
        int sum = calculate(height);
        System.out.println(sum);
    }
    public static int calculate(int[] arr) {
        int L = 0;
        int R = arr.length - 1;
        int MAX_L = 0;
        int MAX_R = 0;
        int sum = 0;
        while (L < R) {
            if (arr[L] < arr[R]) {
                if (arr[L] >= MAX_L) {
                    MAX_L = arr[L];
                }
                sum += MAX_L - arr[L++];
            } else {
                if (arr[R] >= MAX_R) {
                    MAX_R = arr[R];
                }
                sum += MAX_R - arr[R--];
            }
        }
        return sum;
    }
}

完整代码已放到码上上。