42. 接雨水

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

image.png

示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路

image.png

自己在纸上画了一下思路,在上图,黑色虚线表示从左往右搜索的最大值,红色虚线表示从右往左搜索的最大值。有了这两个数组,对每一个柱子(立方体)取left和right最小值,这个最小值就是对应了水面的顶(如果有的话),用这个顶减去当前柱子的高度(水面的底),就是这个位置处对应的水量。由此得到结果。

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        vector<int> left(size), right(size);
        for (int i = 1; i < size; i++)
            left[i] = max(left[i - 1], height[i - 1]);
        for (int i = size - 2; i >= 0; i--)
            right[i] = max(right[i + 1], height[i + 1]);
        int water = 0;
        for (int i = 0; i < size; i++)
        {
            int level = min(left[i], right[i]);
            water += max(0, level - height[i]);
        }
        return water;
    }
};

int main(int argc, char* argv[])
{
    vector<int> test = { 0,1,0,2,1,0,1,3,2,1,2,1 };
    auto res = Solution().trap(test);
    return 0;
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 上面是由数组 ...
    vbuer阅读 900评论 0 1
  • ···class Solution {public int trap(int[] height) {int sum...
    _道友请留步_阅读 252评论 0 0
  • LeetCode 42 接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后...
    Phelthas阅读 522评论 0 0
  • 孙俪的侄女孙怡因为一部《因为遇见你》,瞬间被大家所熟知。在事业发展最好的时候,竟然爆出了怀有身孕。 现在两人的恋情...
    一只草莓味的小可爱阅读 344评论 0 0
  • 大雨,赶往上班途中,脚步匆匆。路过一处牵牛花,雨中恣意绽放,忍不住拍下。
    亦走亦停阅读 264评论 0 0