【Hot100】42. 接雨水

42. 接雨水

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

• 双指针法

1)对于某一个位置i, 我们能否接这个位置上的雨水, 取决于i左右两侧的最大值(leftMax, rightMax)是否比height[i]大,只有当i左右两侧的最大值都比height[i]大时, 才能接i上的雨水, 数量为min(leftMax, rightMax) - height[i];
2) 对于i和j两个指针, i从左向右移动, j从右向左移动, 对于指针i来说, leftMax是真实可信的, 因为leftMax的值是i一步一步走出来的, 但是rightMax是不真实不可信的, 因为i不知道从height[i]到height[j]之间是否有其他的数大于rightMax;同样,对于j来说rightMax是真实可信的, leftMax值是不真实不可信的,即对于左指针i, 它右侧的真实的最大值 >= rightMax, 对于右指针j, 它左侧的真实的最大值 >= leftMax
3) 当出现leftMax rightMax的时候, 右指针的位置是否能接雨水就已经确定了,当left==right时，i和j都可以确定

//双指针法
class