接雨水

算法

题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给定 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

本人提交代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        if ( size == 0 )
            return 0;

        int maxL = 0;
        int maxR = 0;

        int sum = 0;
        int i = 0;
        int j = size - 1;
        while ( i < j )
        {
            if ( height[i] < height[j] )
            {
                if ( height[i] >= maxL )
                    maxL = height[i];
                else
                    sum += maxL - height[i];
                i++;
            }
            else
            {
                if ( height[j] >= maxR )
                    maxR = height[j];
                else
                    sum += maxR - height[j];
                j--;
            }
        }

        return sum;
    }
};

本文由 BeijingJW 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jun 2, 2023 at 05:24 pm