当前位置：首页 > article >正文

LeetCode -Hot100 - 42. 接雨水

article 2025/1/4 11:47:32

前言

本专栏主要通过“LeetCode 热题100”，来捡起自己本科阶段的算法知识与技巧。语言主要使用c++/java。如果同样正在练习LeetCode 热题100的朋友欢迎关注或订阅本专栏。有疑问欢迎留言交流~

题目描述

题目链接
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
在这里插入图片描述
提示：
n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

思路

要求总的雨水量，我们可以把问题拆解。即求单个高度可以蓄多少水，之和即为总水量。那么如何寻找单个高度呢，即左右分别遍历查找，找到比它高的柱子即可。第一版代码如下：

class Solution {
public:
    int findCurHeight(int curi,vector<int>& height){
        int curheight = height[curi];
        int curleftMax = 0;
        int currightMax = 0;
        // 找左边大于i的最大值
        for (int i=0;i<curi;i++){
            curleftMax = max(curleftMax,height[i]);
        }
        // 找右边
        for (int i=curi+1; i<height.size();i++){
            currightMax = max(currightMax,height[i]);
        }
        //cout<<curleftMax<<" "<<currightMax<<endl;
        return max(0,min(curleftMax, currightMax) - curheight);
    }
    int trap(vector<int>& height) {
        int size = height.size();
        int cursum = 0;
        for (int i=1;i<size-1;i++){
            cursum += findCurHeight(i, height);
            //cout<<findCurHeight(i, height);
        }
        return cursum;
    }
};

提交后，发现时间超时，得优化。
优化思路其实也很简单，在计算每个位置的水量时，每次都需要遍历一次左边和右边的元素，导致时间复杂度是 O(n^2)，这会在较大的输入下超时。可以通过预处理左右最大值数组来优化，从而避免重复计算（动态规划）。
具体来说，可以使用两个数组来存储每个位置的左侧最大值和右侧最大值。这样，每个位置的水量计算可以在常数时间内完成。新改版的代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        if (size <= 2) return 0; // 如果只有2个或更少的柱子，无法形成任何水

        vector<int> leftMax(size, 0);
        vector<int> rightMax(size, 0);

        // 填充 leftMax 数组
        leftMax[0] = height[0];
        for (int i = 1; i < size; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        // 填充 rightMax 数组
        rightMax[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        // 计算总的积水量
        int totalWater = 0;
        for (int i = 1; i < size - 1; ++i) {
            // 计算当前位置能够容纳的水量
            int water = min(leftMax[i], rightMax[i]) - height[i];
            if (water > 0) {
                totalWater += water;
            }
        }

        return totalWater;
    }
};