题解 | #接雨水问题#

双指针

首先找到数组中最大值，即最高的木桶效应中的最大值及其对应的下标，然后将数组由此下标划分为左半边和右半边。

1.左半边，left从0开始，right从1开始，只有当left对应的值大于right对应的值时，才可以盛水，如果left小于right对应的值，则将left赋值为right，只要right不大于最大值对应的下标就继续。

2.右半边同理，只不过时从末尾开始到topIndex结束。另外注意只有right对应的值大于 left对应的值时才可以盛水。

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
   public long maxWater (int[] arr) {
        // write code here
        int water = 0;
        int top = 0,topIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            if(top < arr[i]){
            top = arr[i];
            topIndex = i;
            }
        }
        //左侧
        int left = 0,right = 1;
        while (right<=topIndex){
            if(arr[left]>arr[right]){
                water += arr[left]-arr[right];
            }else {
                left = right;
            }
            right++;
        }
        //右侧
        left = arr.length-2;right = arr.length-1;
        while (left>=topIndex){
            if(arr[left]<arr[right]){
                water += arr[right]-arr[left];
            }else {
                right = left;
            }
            left--;
        }
        return water;
    }
}