19.2.4 [LeetCode 42] Trapping Rain Water

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.

19.2.4 [LeetCode 42] Trapping Rain Water
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的思想

19.2.4 [LeetCode 42] Trapping Rain Water
 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

 

上一篇:【CF343D】Water Tree(树链剖分)


下一篇:leetcode 42. Trapping Rain Water