【数据布局与算法】力扣 42. 接雨水

题目描述

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

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

复制代码

示例 2：

1. 输入： height = [4,2,0,3,2,5]
2. 输出： 9

复制代码

提示：

• n == height.length
  
• 1 <= n <= 2 * 104
  
• 0 <= height <= 105
  

分析解答

双指针法解法：

我们使用左右两个指针来遍历数组，维护两个变量 left_max 和 right_max，分别记载从左边和右边柱子的最大高度。通过比力两边的最大高度，确定当前位置能够接到多少水。
原理就是水由左右两个高度最大的值来维护，而真正盘算水又通过这二者间的小值来盘算。

1. function trap(height) {
2.     if (height.length === 0) return 0;
4.     let left = 0;
5.     let right = height.length - 1;
6.     let left_max = 0;
7.     let right_max = 0;
8.     let totalWater = 0;
10.     while (left < right) {
11.         if (height[left] < height[right]) {
12.             if (height[left] >= left_max) {
13.                 left_max = height[left]; // 更新左边最高
14.             } else {
15.                 totalWater += left_max - height[left]; // 计算左边可接水量
16.             }
17.             left++;
18.         } else {
19.             if (height[right] >= right_max) {
20.                 right_max = height[right]; // 更新右边最高
21.             } else {
22.                 totalWater += right_max - height[right]; // 计算右边可接水量
23.             }
24.             right--;
25.         }
26.     }
28.     return totalWater;
29. }
31. // 测试
32. const height1 = [0,1,0,2,1,0,1,3,2,1,2,1];
33. const height2 = [4,2,0,3,2,5];
34. console.log(trap(height1)); // 输出 6
35. console.log(trap(height2)); // 输出 9

复制代码

表明：

• left 和 right 指针分别从数组的两头向中间移动。
  
• 每次移动较低的一侧，并更新该侧的最大高度。
  
• 当前一侧高度小于该侧最大高度时，可以盘算该位置能接的雨水。
  
• 终极，所有的雨水量累加在 totalWater 中。
  

这种解法的时间复杂度是 O(n)，空间复杂度是 O(1)，因为只使用了常数空间。
在这个双指针法解决“接雨水”题目的代码中，有几处涉及到“取等”和“不取等”的情况：
if (height[left] >= left_max) 和 if (height[right] >= right_max)：

• 含义：这两行代码分别是更新左右最大高度的条件。
  
• 取等 (>=)：这两个条件表示当前柱子高度假如大于或即是记载的最大高度，就更新最大高度。原因是：
  
  
  
  • 当 height[left] == left_max 或 height[right] == right_max，此时是无法接水的，因为水只能存储在比最大高度小的柱子位置上。假如当前柱子的高度和最大高度相同（即即是 left_max 或 right_max），我们只需更新最大高度，而不需要盘算水量。这是因为该柱子自身不能存储水，它只会影响后续的接水。
    
  • 因此，这里用 >= 处理，确保即使遇到相等高度，也能正确更新最大高度，避免错误盘算水量。
    
  
  

指针移动时的取等：

• 不取等：在 while (left < right) 中，两个指针的移动条件是 left < right。这里的不取等 (<) 确保指针不会交错或重叠，避免多次盘算同一个位置。我们只希望指针在没有交错的情况下举行移动，因此使用严格小于号。
  

思路拓展


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。