难度: Hard
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
Submission
运行时间: 29 ms
内存: 16.6 MB
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
leftmax = rightmax = -1
res = 0
while left < right:
if height[left] < height[right]:
if height[left] > leftmax:
leftmax = height[left]
else:
res += leftmax - height[left]
left += 1
else:
if height[right] > rightmax:
rightmax = height[right]
else:
res += rightmax - height[right]
right -= 1
return res
Explain
此题解采用双指针法计算直方图中的水量。初始化两个指针，left指向数组的起始位置，right指向数组的结束位置。同时，设置两个变量leftmax和rightmax来记录从左侧和右侧遍历时遇到的最大高度。通过比较两个指针所指向的高度，决定是移动left指针还是right指针。若height[left]小于height[right]，检查当前left指向的高度是否大于leftmax；如果大于，更新leftmax；否则，计算leftmax和当前高度的差值加到结果res中，表示这部分可以积水的量。同理，若height[right]小于或等于height[left]，则检查right指向的高度与rightmax，并作类似处理。这样，直到left与right指针相遇，遍历结束，得到总的积水量。
时间复杂度: O(n)
空间复杂度: O(1)
# 定义类Solution
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1 # 初始化左右指针
leftmax = rightmax = -1 # 初始化左右最大值
res = 0 # 初始化结果变量
while left < right: # 当左指针小于右指针时循环
if height[left] < height[right]: # 若左边的高度小于右边
if height[left] > leftmax: # 检查是否更新左边最大值
leftmax = height[left]
else:
res += leftmax - height[left] # 累加积水量
left += 1 # 移动左指针
else: # 若左边的高度不小于右边
if height[right] > rightmax: # 检查是否更新右边最大值
rightmax = height[right]
else:
res += rightmax - height[right] # 累加积水量
right -= 1 # 移动右指针
return res # 返回结果
Explore
这种选择的关键在于保证在移动指针时能够确定积水的边界。当height[left] < height[right]时，可以确定左侧的界定边界（leftmax）是有效的，因为即使右侧存在更高的边界，它也不会影响左侧已经确定的积水界限。因此，可以安全地移动left指针，来更新或计算该位置的积水情况。相反，当height[right] <= height[left]时，右侧边界（rightmax）是可靠的，因为左侧的高度不会影响右侧的积水计算。这样的处理确保了在每一步中都能通过leftmax或rightmax准确计算积水量，而不需要担心另一侧可能的更高边界。
是的，初始化leftmax和rightmax为-1的确是基于所有直方图高度是非负值的假定。在现实应用中，直方图高度通常代表物理量度如水位或物体的高度，因此通常是非负的。如果直方图中存在负值，则该算法可能不适用，因为它在计算积水量时是基于高度差（leftmax和rightmax与当前高度的差值）来计算的，这在高度为负时逻辑上会出现问题。
是的，该计算方法考虑了两边高度不一致的情况。通过双指针法和leftmax以及rightmax的更新机制，算法确保了不论两边的高度差异如何，都可以正确地计算出每个位置可能的积水量。当某一端明显高于另一端时，更高的一端的最大值（leftmax或rightmax）会控制积水的最大可能量，而较低的一端则逐步更新其最大值并计算差值作为积水量。这种处理方式允许算法在处理非均匀高度分布时仍然能够准确地计算出积水总量。