【题解】【直方图】【Leetcode】Trapping Rain Water

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.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

【题解】【直方图】【Leetcode】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!

 

思路:

O(n) solution. for each bar, find the max height bar on the left and right. then for this bar it can hold min(max_left, max_right) - height

对于任何一个坐标,检查其左右的最大坐标,然后相减就是容积。所以,
1. 从左往右扫描一遍,对于每一个坐标,求取左边最大值。
2. 从右往左扫描一遍,对于每一个坐标,求最大右值。

代码:

【题解】【直方图】【Leetcode】Trapping Rain Water
 1 class Solution {
 2 public:
 3     int trap(int A[], int n) {
 4         if(n < 3) 
 5             return 0;        
 6         vector<int> maxRs(n);  
 7         int maxR = 0;
 8         for(int i = 0; i < n; i++){
 9             if(A[i] > maxR) 
10                 maxR = A[i];
11             maxRs[i] = maxR;
12         }
13         
14         int totalV = 0;
15         int maxL = 0;
16         for(int i = n-1; i >= 0; i--){
17             if(A[i] > maxL) 
18                 maxL = A[i];
19             totalV += min(maxL, maxRs[i]) - A[i];
20         }
21         return totalV;
22     }
23 };
【题解】【直方图】【Leetcode】Trapping Rain Water

【题解】【直方图】【Leetcode】Trapping Rain Water

上一篇:使用tcpdump和wireshark对android手机进行网络抓包分析


下一篇:android SystemUI导入eclipse 编译