By Long Luo
Leetcode 42. 接雨水 题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 42. 接雨水 给定$n$个非负整数表示每个宽度为$1$的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1:  输入: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 * 10^4 0 <= height[i] <= 10^5
方法一: 按列求(木桶原理)
思路与算法:
很容易想到,装水的多少,根据木桶原理 ,只需要关注左边最高的木板和右边最高的模板中较矮的一个就够了,那么存储的水,等于两边木板的较小值减去当前高度的值。
从左向右遍历数组:
从当前元素向左扫描并更新:max_left = max ( max_left , height [ j ] ) \text{max\_left}=\max(\text{max\_left}, \text{height}[j]) max_left = max ( max_left , height [ j ] )
从当前元素向右扫描并更新:max_right = max ( max_right , height [ j ] ) \text{max\_right}=\max(\text{max\_right}, \text{height}[j]) max_right = max ( max_right , height [ j ] )
更新 ans + = min ( max_left , max_right ) − height [ i ] \text{ans} += \min(\text{max\_left}, \text{max\_right}) - \text{height}[i] ans + = min ( max_left , max_right ) − height [ i ] 。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public static int trap (int [] height) { if (height == null || height.length <= 2 ) { return 0 ; } int ans = 0 ; int len = height.length; for (int i = 1 ; i < len - 1 ; i++) { int maxRight = 0 ; int maxLeft = 0 ; for (int right = i; right < len; right++) { maxRight = Math.max(maxRight, height[right]); } for (int left = i; left >= 0 ; left--) { maxLeft = Math.max(maxLeft, height[left]); } ans += Math.min(maxLeft, maxRight) - height[i]; } return ans; }
复杂度分析:
时间复杂度:O ( n 2 ) O(n^2) O ( n 2 ) ,遍历每一列需要 n n n ,找出左边最高和右边最高的木板加起来刚好又是一个 n n n ,所以是 n 2 n^2 n 2 。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法二:按行求
思路与算法:
求第 i i i 层的水,遍历每个位置,如果当前的高度小于 i i i ,并且两边有高度大于等于 i i i 的,说明这个地方一定有水,水就可以加 1 1 1 。
如果求高度为 i i i 的水,首先用一个变量 w a t e r water w a t e r 保存当前累积的水,初始化为 0 0 0 。从左到右遍历墙的高度,遇到 h ≥ i h \ge i h ≥ i 的时候,开始更新 w a t e r water w a t e r 。
第一次遇到已经开始计算时并且 h < i h < i h < i 的就把 w a t e r + 1 water+1 w a t e r + 1 ,再次遇到 h ≥ i h \ge i h ≥ i 的,说明这个地方一定有水,就把 w a t e r water w a t e r 加到最终的答案 a n s ans a n s 里,w a t e r = 0 water=0 w a t e r = 0 ,f l a g = f a l s e flag=false f l a g = f a l s e ,然后继续循环。
代码如下所示:
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 public static int trap_row (int [] height) { if (height == null || height.length <= 2 ) { return 0 ; } int ans = 0 ; int len = height.length; int maxHeight = 0 ; for (int x : height) { maxHeight = Math.max(maxHeight, x); } for (int i = 1 ; i <= maxHeight; i++) { boolean flag = false ; int water = 0 ; for (int j = 0 ; j < len; j++) { if (flag && height[j] < i) { water++; } if (height[j] >= i) { ans += water; water = 0 ; flag = true ; } } } return ans; }
复杂度分析:
时间复杂度:O ( m a x H e i g h t × n ) O(maxHeight \times n) O ( m a x H e i g h t × n ) ,其中 m a x H e i g h t maxHeight m a x H e i g h t 是数组元素的最大值。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法三:动态规划
思路与算法:
方法一中对于每一列,我们求它左边最高的木板和右边最高的木板,都需要遍历一遍所有高度,这里可以优化一下。
我们使用两个数组,l e f t M a x [ i ] leftMax[i] l e f t M a x [ i ] 代表第 i i i 列左边最高的木板的高度,r i g h t M a x [ i ] rightMax[i] r i g h t M a x [ i ] 代表第 i i i 列右边最高的木板的高度,注意这里第 i i i 列左(右)边最高的木板,是不包括自身的。
l e f t M a x [ i ] = M a x . m a x ( l e f t M a x [ i − 1 ] , h e i g h t [ i − 1 ] ) leftMax[i] = Max.max(leftMax[i-1], height[i-1]) l e f t M a x [ i ] = M a x . m a x ( l e f t M a x [ i − 1 ] , h e i g h t [ i − 1 ] ) ,当前列左边最高的木板要么是它左边的木板,要么是左边木板左边的最高高度。
同理 r i g h t M a x [ i ] = M a t h . m a x ( m a x r i g h t [ i + 1 ] , h e i g h t [ i + 1 ] ) rightMax[i] = Math.max(max_right[i+1], height[i+1]) r i g h t M a x [ i ] = M a t h . m a x ( m a x r i g h t [ i + 1 ] , h e i g h t [ i + 1 ] ) 。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public static int trap_dp (int [] height) { if (height == null || height.length <= 2 ) { return 0 ; } int ans = 0 ; int len = height.length; int [] leftMax = new int [len]; int [] rightMax = new int [len]; for (int i = 1 ; i < len - 1 ; i++) { leftMax[i] = Math.max(leftMax[i - 1 ], height[i - 1 ]); } for (int i = len - 2 ; i >= 0 ; i--) { rightMax[i] = Math.max(rightMax[i + 1 ], height[i + 1 ]); } for (int i = 1 ; i < len - 1 ; i++) { int min = Math.min(leftMax[i], rightMax[i]); ans += min > height[i] ? min - height[i] : 0 ; } return ans; }
复杂度分析:
时间复杂度:O ( n ) O(n) O ( n ) 。
空间复杂度:O ( n ) O(n) O ( n ) 。
方法四:双指针
思路与算法:
一般来说,动态规划的空间复杂度都可以进行优化。从方法三也可以看出,l e f t M a x [ i ] leftMax[i] l e f t M a x [ i ] 和 r i g h t M a x [ i ] rightMax[i] r i g h t M a x [ i ] 数组中的元素其实只用到了一次,所以可以只用一个元素就行了。
很容易写出如下代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public static int trap_tp (int [] height) { if (height == null || height.length <= 2 ) { return 0 ; } int len = height.length; int ans = 0 ; int leftMax = height[0 ]; int [] rightMax = new int [len]; for (int i = len - 2 ; i >= 0 ; i--) { rightMax[i] = Math.max(rightMax[i + 1 ], height[i + 1 ]); } for (int i = 1 ; i < len - 1 ; i++) { leftMax = Math.max(leftMax, height[i]); int min = Math.min(leftMax, rightMax[i]); ans += min > height[i] ? min - height[i] : 0 ; } return ans; }
上述代码的空间复杂度还是 O ( n ) O(n) O ( n ) ,如何才能把 r i g h t M a x rightMax r i g h t M a x 的数组也去掉呢?
因为从左往右处理到 i i i 下标时,左边的最大值 l e f t M a x leftMax l e f t M a x 是可信的,因为 r i g h t M a x rightMax r i g h t M a x 是从右往左遍历的,所以需要 r i g h t M a x rightMax r i g h t M a x 数组来记录右边最大值。
基于此,要用到两个指针,l e f t left l e f t 和 r i g h t right r i g h t ,从两个方向去遍历。
如果一端有更高的木板,那么水的高度依赖于当前方向的高度(从左到右),而当我们发现另一侧(右侧)的木板不是最高的,则开始从相反的方向遍历(从右到左)。
我们可以只需要 1 1 1 次遍历,在遍历时同时维护 leftMax \text{leftMax} leftMax 和 rightMax \text{rightMax} rightMax ,代码如下所示:
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 public static int trap_tp_opt (int [] height) { if (height == null || height.length <= 2 ) { return 0 ; } int len = height.length; int ans = 0 ; int left = 0 ; int right = len - 1 ; int leftMax = height[0 ]; int rightMax = height[right]; while (left < right) { if (height[left] < height[right]) { leftMax = Math.max(leftMax, height[left]); ans += leftMax - height[left]; left++; } else { rightMax = Math.max(rightMax, height[right]); ans += rightMax - height[right]; right--; } } return ans; }
复杂度分析:
时间复杂度:O ( n ) O(n) O ( n ) 。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法五:单调栈
思路与算法:
遍历到某些木板的时候,会由于和之前的某个木板形成凹形的坑,从而可以接住雨水,所以这道题目可以用单调栈 来做。
单调栈就是比普通的栈多一个性质,即维护一个栈内元素单调。使用单调栈来解,和方法二类似,但又有所区别。具体到这道题,单调栈存储的是下标,满足从栈底到栈顶的下标对应的 height [ i d x ] \textit{height}[idx] height [ i d x ] 递减。
从左到右遍历数组,遍历到下标 i i i 时,如果栈内至少有两个元素,记栈顶元素为 top \textit{top} top ,top \textit{top} top 的下面一个元素是 left \textit{left} left ,则一定有 height [ left ] ≥ height [ top ] \textit{height}[\textit{left}] \ge \textit{height}[\textit{top}] height [ left ] ≥ height [ top ] 。如果 height [ i ] > height [ top ] \textit{height}[i]>\textit{height}[\textit{top}] height [ i ] > height [ top ] ,则得到一个可以接雨水的区域,该区域的宽度是 i − left − 1 i-\textit{left}-1 i − left − 1 ,高度是 min ( height [ left ] , height [ i ] ) − height [ top ] \min(\textit{height}[\textit{left}], \textit{height}[i])-\textit{height}[\textit{top}] min ( height [ left ] , height [ i ] ) − height [ top ] ,根据宽度和高度即可计算得到该区域能接的雨水量。
为了得到 left \textit{left} left ,需要将 top \textit{top} top 出栈。在对 top \textit{top} top 计算能接的雨水量之后,left \textit{left} left 变成新的 top \textit{top} top ,重复上述操作,直到栈变为空,或者栈顶下标对应的 height \textit{height} height 中的元素大于或等于 height [ i ] \textit{height}[i] height [ i ] 。
在对下标 i i i 处计算能接的雨水量之后,将 i i i 入栈,继续遍历后面的下标,计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public static int trap_stack_opt (int [] height) { int ans = 0 ; Deque<Integer> stack = new LinkedList <Integer>(); int len = height.length; for (int i = 0 ; i < len; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) { break ; } int left = stack.peek(); int currWidth = i - left - 1 ; int currHeight = Math.min(height[left], height[i]) - height[top]; ans += currWidth * currHeight; } stack.push(i); } return ans; }
复杂度分析:
时间复杂度:O ( n ) O(n) O ( n ) 。
空间复杂度:O ( n ) O(n) O ( n ) 。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗