首页 > 移动平台 > 详细

19.2.4 [LeetCode 42] Trapping Rain Water

时间:2019-02-04 14:22:50      阅读:164      评论:0      收藏:0      [点我收藏+]

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.

技术分享图片
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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

题解

我觉得这题还挺难的,是我还没有深刻get的思想

技术分享图片
 1 class Solution {
 2 public:
 3     int trap(vector<int>& height) {
 4         int ans = 0, size = height.size(), i = 0;
 5         stack<int>q;
 6         while (i < size) {
 7             if (q.empty()||height[i]<=height[q.top()]) {
 8                 q.push(i++);
 9                 continue;
10             }
11             else {
12                 int now = q.top(); q.pop();
13                 if (q.empty())continue;
14                 ans += (min(height[i], height[q.top()]) - height[now])*(i - q.top() - 1);
15             }
16         }
17         return ans;
18     }
19 };
View Code

 

19.2.4 [LeetCode 42] Trapping Rain Water

原文:https://www.cnblogs.com/yalphait/p/10351713.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!