登山则情满于山,观海则意溢于海。这篇文章主要讲述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】
推荐阅读
- Android-Java-静态变量与静态方法&普通变量与普通方法(内存图 完整版)
- Android-普通变量与普通方法内存图
- Android-Java-静态变量
- Android-Java-构造函数间调用&this内存图
- 理解Android View的事件传递机制
- 高通开源android源码下载
- 微信表情有一根毛是啥意思?_微信
- 微信视频怎样美颜?微信视频美颜打开办法_微信
- 微信垃圾怎样清理?微信垃圾清理办法_微信