19.2.4 [LeetCode 42] Trapping Rain Water

登山则情满于山,观海则意溢于海。这篇文章主要讲述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

文章图片
19.2.4 [LeetCode 42] Trapping Rain Water

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

View Code【19.2.4 [LeetCode 42] Trapping Rain Water】 

    推荐阅读