【LeetCode力扣】42.接雨水（困难）_业界新闻

发布时间:2024-08-07 22:35

阅读量:0

1、题目介绍

原题链接：42. 接雨水 - 力扣（LeetCode）

输入：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

提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

2、解题

2.1、解题思路

一个用木板围成的桶能装多少水取决于最短的那块木板，同理，这道题我们可以把它看做成是由若干块木板组成的一个桶，只是它们是以并排的方式组成的，这里我用left和right两个指针分别指向最左和最右的两块木板，用变量 sum 来记录总的装水量以及两个变量leftMax和rightMax来记录左边最高的木板值和右边最高的木板值，哪一边的 (left / right)Max 更小就用哪边的 (left / right)Max 减去 (left / right)所指的值，这样就能求出指针移动一次的装水量了。初始时 left = 0; right = n-1 (n就是数组的长度)，leftMax = 0；rightMax = 0 。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中决定两个变量 leftMax 和 rightMax 的值。

当 left 小于 right 的时候，也就是两个指针没有相遇之前，进行的操作如下：
（1）使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；就是 leftMax 记录 left 从左往右所指过的值中的最大值；rightMax 记录 right 从右往左所指过的值中的最大值，即执行：leftmax = Math.max(leftmax, height[left]); rightmax = Math.max(rightmax, height[right]);
（2）如果 height[left] < height[right]，则必有 leftMax < rightMax，下标 left 处能接的雨水量等于 leftMax − height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）即执行：sum += leftmax - height[left]; left++;
（3）如果 height[left] ≥ height[right]，则必有 leftMax≥rightMax，下标 right 处能接的雨水量等于 rightMax − height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）即执行：sum += rightmax - height[right]; right--;

2.2、图解说明

定义一个数组，height = [0,1,0,2,1,0,1,3,2,1,2,1]

2.3、解题代码

class Solution {     public int trap(int[] height) {         int left = 0;         int right = height.length-1;         int sum = 0;         int leftmax = 0;         int rightmax = 0;         while(left < right){             leftmax = Math.max(leftmax, height[left]);             rightmax = Math.max(rightmax, height[right]);             if(height[left] < height[right]){                 sum += leftmax - height[left];                 left++;             } else{                 sum += rightmax - height[right];                 right--;             }         }         return sum;     } }