力扣——接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

双指针

思路

使用双指针遍历的方法，在遍历的过程中，寻找大小不同的两根柱子（一个指针不动，另一个指针去找），计算这两根柱子接水容量，然后继续寻找下一组，最后全部相加即得到能给接的雨水量。

解题方法

首先找到特殊情况，当数组数量小于3时，必然不可能形成凹槽接到雨水。然后定义两个双指针（一个stay指针指向当前柱子，一个move指针往后寻找符合条件的柱子），在move指针移动的过程中，将不符合条件的柱子高度累加到一个offset变量中，在move指针找到符合条件的柱子后，stay指针指向的柱子高度乘上两个指针的距离再减去offset即可得到一个符合条件的容量数据。同时还要考虑当move指针已经指向最后一个柱子时却没有找到一个高度小于等于stay指针指向的柱子时，需要从数组末尾开始逆向遍历，用相同的方法得到最后一个容量数据

Code

class Solution {
    public int trap(int[] height) {
 if (height.length < 3){
            return 0;
        }
        int maxCapacity = 0;
        int stay = 0;
        int move = stay + 1;
        int offset = 0;
        while (move < height.length){
            if (move == height.length - 1 && height[stay] >= height[move]){//需要逆向遍历的特殊情况
                int newOffset = 0;
                int newStay = move;
                int newMove = newStay - 1;
                while (newMove >= stay){
                    if (height[newStay] <= height[newMove]){
                        maxCapacity += height[newStay] * (newStay - newMove - 1) - newOffset;
                        newOffset = 0;
                        newStay = newMove--;
                        continue;
                    }
                    newOffset += height[newMove];
                    newMove--;
                }
                break;
            }

            if (height[stay] <= height[move]){
                maxCapacity += height[stay] * (move - stay - 1) - offset;
                offset = 0;
                stay = move++;
                continue;
            }

            offset += height[move];
            move++;
        }

        return maxCapacity;
    }
}