deftrapping_rain_water(heights): ans = 0 i, j = 0, len(heights) - 1 ml, mr = 0, 0
while i <= j: hi, hj = heights[i], heights[j]
# 对 i 来说 ml 总是对的, mr 却不一定是对的. 但是如果 mr >= ml, mr 对不对也无所谓了. if mr >= ml: ans += max(ml - hi, 0) if hi > ml: ml = hi i += 1 # 对 j 来说 mr 总是对的, ml 却不一定是对的. 但是如果 ml >= mr, ml 对不对也无所谓了. else: ans += max(mr - hj, 0) if hj > mr: mr = hj j -= 1
deftrapping_rain_water(heights): stack = [] ans = 0 for i, h inenumerate(heights): while stack and heights[stack[-1]] < h: j = stack.pop() ifnot stack: break ans += (i - stack[-1] - 1) * (min(heights[stack[-1]], h) - heights[j]) stack.append(i)
deflargest_rectangle_in_histogram(heights): stack = [] heights = [0] + heights + [0] ans = 0 for i, h inenumerate(heights): while stack and heights[stack[-1]] > h: j = stack.pop() s = heights[j] * (i - stack[-1] - 1) if s > ans: ans = s stack.append(i)