LeetCode 42

思路

经典的双指针问题，首先让左右两指针分别指向数组的头和尾，并维护两个变量，left_max和right_max用来存储当前左侧和右侧的最大值。假设，当前左侧的柱形高度低于右侧，那么如果左侧的柱形低于left_max的高度，那么当前柱形的上方一定能积水，否则，一定没有积水，那么我们就将left_max的高度更新为当前柱形的高度。右侧同理。那么用此方法，使用双指针遍历完所有的柱形之后，总的积水量就可以得出来了。