宁可枝头抱香死,何曾吹落北风中。这篇文章主要讲述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
【LeetCode-42-Trapping Rain Water】解题思路:两个指针分别从两端开始扫,直到相遇。再用额外的两个变量标记两端最高位,当当前指针所指变量的值低于最高变量,则增加结果。
int trap(vector< int> & height) { if(height.size()< 2) return 0; int left = 0; int right = height.size()-1; int maxLeft =0; int maxRight = 0; int res = 0; while(left < right){ if(height[left] < height[right]){ if(height[left] > maxLeft) maxLeft = height[left]; else res += maxLeft- height[left]; left++; }else{ if(height[right] > maxRight) maxRight = height[right]; else res += maxRight - height[right]; right--; } } return res; }
推荐阅读
- Android 引导页的代码
- Approximate timing for various operations on a typical PC
- Android Api 27 在 Android 8.0 上出现 Only fullscreen opaque activities can request orientation 的解决情况(代码片
- Android的对话框DialogFragment指定弹窗口大小,设置圆角
- Saliency Detection: A Spectral Residual Approach
- No mapping found for HTTP request with URI [/spring_liu/hello.do] in DispatcherServlet with name 
- ???Android???11.0 UI?????????????????????????????????ListView???????????????2
- Android内存泄漏的检测流程捕捉以及分析
- Flutter项目之app升级方案