接雨水

题目详情

双指针法、栈解法

解题思路

双指针法

看到个很精妙的双指针法，在计算每个 i 可以装多少水的时候，其实只关注左右两侧最小的那个，
也就是说 height[i]能够装的水只和较低的 l_max 之差有关

• TypeScript 实现

function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = height[left];
  let rightMax = height[right];
  let res = 0;
  while (left <= right) {
    leftMax = Math.max(leftMax, height[left]);
    rightMax = Math.max(rightMax, height[right]);
    if (leftMax < rightMax) {
      res += leftMax - height[left];
      left++;
    } else {
      res += rightMax - height[right];
      right--;
    }
  }
  return res;
}

• Python 实现

        ## 双指针法 时间复杂度O(n) 空间复杂度O(1)
        ## 其实这个问题要这么思考，我们只在乎min(l_max, r_max)。对于上图的情况，
        ## 我们已经知道l_max < r_max了，至于这个r_max是不是右边最大的，不重要。
        ## 重要的是height[i]能够装的水只和较低的l_max之差有关：
        left = 0
        right = len(height) - 1
        ## 记录左右的最大值
        l_max = height[left]
        r_max = height[right]
        res = 0
        while left <= right:
            l_max = max(l_max, height[left])
            r_max = max(r_max, height[right])
            ## res取决于左右最短的那根柱子
            if l_max < r_max:
                res += l_max - height[left]
                left += 1
            else:
                res += r_max - height[right]
                right -= 1
        return res

栈解法

分为三种情况：

1. 如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
2. 如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
3. 如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了（这种情况会出现雨水）
   实质是：栈顶和栈顶的下一个元素以及要入栈的三个元素来接水！

• TypeScript 实现

  let stack: number[] = [];
  let res = 0;
  for (let i = 0; i < height.length; i++) {
    // 当栈不为空，且当前元素大于栈顶元素时，说明可以接雨水，开始出栈
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      let top = stack.pop()!; //!为非空断言
      if (!stack.length) break; //如果此时栈为空，说明无法接雨水
      const h = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
      const w = i - stack[stack.length - 1] - 1;
      res += h * w;
    }
    stack.push(i);
  }
  return res;

• Python 实现

        ## 栈解法 时间复杂度O(n) 空间复杂度O(n)
        stack = []
        res = 0
        for index, val in enumerate(height):
            ## 如果栈不为空并且当前柱子的高度大于栈顶的柱子高度
            while stack and val > height[stack[-1]]:
                ## 弹出栈顶元素
                top = stack.pop()
                ## 如果栈为空，说明没有左边界，直接跳出循环
                if not stack:
                    break
                ## 计算高度和宽度
                h = min(val, height[stack[-1]]) - height[top]
                w = index - stack[-1] - 1
                res += h * w
            stack.append(index)
        return res