算法思路:双指针从两端向中间移动,每次处理较低的一侧
1. 双指针初始化:left 指向最左侧,right 指向最右侧
2. 维护最大值:leftMax 记录左侧最大高度,rightMax 记录右侧最大高度
3. 处理较低的一侧:如果 height[left] < height[right],说明 left 侧的接水量已确定(因为右面有更高的墙)
4. 计算接水量:当前位置能接的水量 = 当前侧的最大值 - 当前高度。如果为负则不接水
5. 移动指针:处理完后移动对应的指针,继续直到相遇
时间复杂度:O(n),空间复杂度:O(1)