接雨水

发表于 | 分类于 |
字数统计: 473 字 | 阅读时长 ≈ 1 分钟

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

双指针

  • 两指针指向数组两边，声明两边的最大值
  • 比较指针所指的值，哪个小就移动
  • 移动之前，比较当前值和最大值
    • 当前值大，则设为最大值
    • 当前值小，则给结果加上 最大值-当前值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var trap = function (height) {
  let left = 0, right = height.length - 1; //左右指针
  let leftMax = 0, rightMax = 0; //左右最大高度
  let res = 0;
  while (left < right) {
    //左右值
    const leftVal = height[left];
    const rightVal = height[right];
    //左值小 让左指针右移； 否则右值小 右指针左移；
    if (leftVal <= rightVal) {
      left++;
      // 如果左值大于左边最大值； 更新左边最大值；
      if (leftVal > leftMax) {
        leftMax = leftVal;
      } else if (leftVal < leftMax) {
        //否则如果左值小于左边最大值； 结果res加上 左边最大值减去左值；
        res += leftMax - leftVal;
      }
    } else {
      right--;
      // 如果右值大于右边最大值； 更新右边最大值；
      if (rightVal > rightMax) {
        rightMax = rightVal;
      } else if (rightVal < rightMax) {
        //否则如果右值小于右边最大值； 结果res加上 右边最大值减去右值；
        res += rightMax - rightVal;
      }
    }
  }
  return res;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
  • 空间复杂度：O(1)。只需要使用常数的额外空间。

单调栈

动态规划