【Leetcode】

题目传送门

方法一： 前缀和+后缀和

算法原理

需要两个数组。 第一个数组存储最左边到第 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

代码：

代码语言：javascript代码运行次数：0运行复制
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）

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

算法原理

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

代码：

代码语言：javascript代码运行次数：0运行复制
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;
    }
}

复杂度分析

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

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-01-24，如有侵权请联系 cloudcommunity@tencent 删除数组原理存储intleetcode