【Leetcode】--- 接雨水

用户11288958

发布于 2025-01-27 00:14:37

25800

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

题目传送门

方法一：前缀和+后缀和

算法原理

需要两个数组。第一个数组存储最左边到第 i 个位置的最大高度（前缀最大值）第二个数组存储最右边到第 i 个位置的最大高度（后缀最大值）最终第 i 个位置的接水量 = min（第 i 位置的前缀最大值，第 i 位置的后缀最大值）- 第 i 位置的高度
例如上示例： height = 0,1,0,2,1,0,1,3,2,1,2,1 前缀最大值 = 0,1,1,2,2,2,2,3,3,3,3,3 后缀最大值 = 3,3,3,3,3,3,3,3,2,2,2,1 最终求得 0,0,1,0,1,2,1,0,0,1,0,0 累加得6

代码：

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = height[0];
        g[n-1] = height[n-1];
        int sum = 0;

        for(int i = 1; i < n; i++){
            f[i] = Math.max(height[i],f[i-1]);  
        }
        for(int i = n-2; i >= 0; i--){
            g[i] = Math.max(height[i],g[i+1]);  
        }

        for(int i = 0; i < n; i++){
            sum += Math.min(f[i],g[i]) - height[i];
        }
        return sum;
    }
}

复杂度分析

时间复杂度：O（n）空间复杂度：O（n）

解法二：双指针（法一的优化）

算法原理

如果左边前缀最大值比右边前缀最大值小，那么接水量就是左边前缀最大值 - 当前高度如果左边前缀最大值比右边前缀最大值大，那么接水量就是右边前缀最大值 - 当前高度

代码：

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