Trapping Rain Water1,2 优先队列解法

来源:http://www.sh-fengwen.com 作者:家常菜谱 人气:189 发布时间:2019-09-05
摘要:标签: C++ 算法 LeetCode 数组 每日算法——leetcode系列 class Solution {public: int trap(vectorint height) { pairint,int que; int len = height.size(); if return 0; int res = 0; que.first = 0; que.second = len-1; int Max = -1;

标签: C++ 算法 LeetCode 数组

每日算法——leetcode系列


class Solution {public: int trap(vector<int>& height) { pair<int,int> que; int len = height.size(); if return 0; int res = 0; que.first = 0; que.second = len-1; int Max = -1; while(que.first<que.second) { //Max = max(height[que.first],height[que.second]); if(height[que.first]<=height[que.second]) { if(height[que.first]>Max) Max = height[que.first]; if(Max>height[que.first+1]) res+=Max - height[que.first+1]; que.first++; } else { if(Max<height[que.second]) Max = height[que.second]; if(Max>height[que.second-1]) res+= Max-height[que.second-1]; que.second--; } } return res; }};

问题 Trapping Rain Water

Difficulty: Hard

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

图片 1


<small>The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!</small>

class Solution {
public:
    int trap(vector<int>& height) {

    }
};

翻译

本文由美高梅游戏平台网站发布于家常菜谱,转载请注明出处:Trapping Rain Water1,2 优先队列解法

关键词:

最火资讯