42. 接雨水暴力法、双指针

绝地灬酷狼 2023-02-08 12:48 91阅读 0赞

链接：https://leetcode-cn.com/problems/trapping-rain-water

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

示例1  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]

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

## 题目分析 ##

这道题有3种做法。暴力法、最小栈、双指针。  
本文列举暴力法，面试用来保底。  
以及双指针，用于优化，时间复杂度从 O(n^2) 直降到 O(n)。

### 暴力法 ###

有没有同学，写不出暴力法的？  
把 height\[i\] 当成一个木桶，咱们一个一个地看。  
短板理论：容量取决于最短的木板。

对于一个桶，

1.  先找到左右两边，最高的木板
2.  然后，两者相权取其短
3.  (高度 - 底部的厚度) \* 宽度 = 每个桶的容量

最后累加得答案。

对于每个桶，怎么找左右的木板呢？

1.  向左遍历
2.  向右遍历

class Solution {
        
        public int trap(int[] height) {
        
            int size = height.length;
            int ans = 0;
            for (int i = 1; i < size; i++) {
        
                int maxLeft = 0; int maxRight = 0;
                // 找左边的高板
                for (int j = i ; j >= 0 ; j--) {
        
                    maxLeft = Math.max(maxLeft, height[j]);
                }
                // 找右边的高板
                for (int k = i; k < size; k++) {
        
                    maxRight = Math.max(maxRight, height[k]);
                }
                // 取短板，乘以高度（恒为1）
                ans += Math.min(maxLeft,maxRight) - height[i];
            }
            return ans;
        }
    }

## 双指针 ##

好，理解了暴力法，可以做出来了，就是时间复杂度高达 n 的平方。

我们换个思路来想问题

就拿一个左边的桶 height \[ left \] 来说，当我们知道左板高度，其实没必要细致地，找到相邻的右板。

只需要确定，**右边有更高的木板，水不会溢出**。

假设 left\_max , right\_max 分别代表左右两边的高度

对于位置left而言，它左边最大值一定是left\_max，右边最大值“大于等于”right\_max，这时候，如果left\_max<right\_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right\_max，都不影响这个结果（[细节分析][Link 1]）。

这时可以计算桶容量了，而不用再浪费时间遍历右边的木板。

class Solution {
        
        public int trap(int[] height) {
        
    
            int size = height.length;
            int ans = 0;
            int left = 0; int right = size-1; // 指针
            int maxLeftHeight = 0; int maxRightHeigh = 0; // 高度
            while (left <= right) {
        
                if (maxLeftHeight < maxRightHeigh) {
        
                    ans += Math.max(0, maxLeftHeight - height[left]);
                    maxLeftHeight = Math.max(maxLeftHeight, height[left]);
                    left++;
                } else {
        
                    ans += Math.max(0, maxRightHeigh - height[right]);
                    maxRightHeigh = Math.max(maxRightHeigh, height[right]);
                    right--;
                }
            }
            return ans;
        }
    }

时间复杂度：O(n)  
空间复杂度：O(1)

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
双指针法一次遍历，性能甩暴力法9条街

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230208/97eaccb05147446d9c55bbf0bad5b146.png
[Link 1]: https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/327718
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20230208/2a1054fbc05f4a889e210bbe538e667e.png