力扣 42. 接雨水 python AC

双指针

class Solution:def trap(self, heights):l, r = 0, len(heights) - 1maxl, maxr = 0, 0ans = 0while l < r:maxl, maxr = max(maxl, heights[l]), max(maxr, heights[r])if maxl < maxr:ans += maxl - heights[l]l += 1else:ans += maxr - heights[r]r -= 1return ans

单调栈

class Solution:def trap(self, heights):ll = []ans = 0for ind, val in enumerate(heights):while ll and val >= heights[ll[-1]]:bottom = heights[ll.pop()]if ll:h = min(heights[ll[-1]], val) - bottomans += h * (ind - ll[-1] - 1)ll.append(ind)return ans

（单调栈做法：）

--创建空列表作为栈（每轮将当前元素索引加入栈）

--遍历

  --（while）如果栈不为空且当前元素值大于等于栈中最后一位索引的值

    --弹出栈中最后一位索引并将该索引代表的值设为底的高度

    --如果栈不为空（如果为空说明左边接不了水，直接退出）

      --求出高h为（上一步弹出后）栈内最后一位索引的值和当前加入栈的值的最小值-底的高度

      --将高h*（当前加入值的索引-栈内最后一位索引-1，即两根柱子的距离）计入总和

  --（此时每轮结束）将此新元素索引加入栈