双指针

难度困难

题目描述

解题思路

缓存两端最大值，从最大值较小的一边进行储水结算、移动，并更新最大值。

Code

public int trap(int[] height) {
    //长度为1或者2时，蓄水量一定为0
    if (height.length < 3) {
        return 0;
    }
    //长度大于2的情况
    int left = 0;//左指针
    int right = height.length - 1;//右指针
    int leftmax = height[left];//左边最大值
    int rightmax = height[right];//右边最大值
    int res = 0;//记录蓄水量
    while (left < right) {
        if (leftmax < rightmax) {
            //左侧最高值减去当前位置值就是该位置的蓄水量
            res += leftmax - height[left++];
            //更新左侧最大值
            leftmax = Math.max(leftmax, height[left]);
        } else {
            //右侧最高值减去当前位置值就是该位置的蓄水量
            res += rightmax - height[right--];
            //更新右侧最大值
            rightmax = Math.max(rightmax, height[right]);
        }
    }
    //注：某位置的蓄水量等于当前最高值减去该位置的值
    return res;
}