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.

文章图片

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: 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】