【Leetcode】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. 

【Leetcode】Trapping Rain Water
 1 class Solution {
 2 public:
 3     int trap(int A[], int n) {
 4         int sum = 0;
 5         int *max_left = new int[n]();
 6         for (int i = 1; i < n - 1; ++i) {
 7             if (A[i - 1] > max_left[i - 1]) {
 8                 max_left[i] = A[i - 1];
 9             } else {
10                 max_left[i] = max_left[i - 1];
11             }
12         }
13         int max_right = 0;
14         for (int i = n - 2; i >= 1; --i) {
15             if (A[i + 1] > max_right) {
16                 max_right = A[i + 1];
17             }
18             if (A[i] < max_left[i] && A[i] < max_right) {
19                 sum += (min(max_left[i], max_right) - A[i]);
20             }
21         }
22         return sum;
23     }
24 };
View Code

单独考虑每根bar,每根bar上方可以盛的水量取决于从它向扫描到的最的bar和向扫描到的最的bar中较的那一个和它本身的高度差。

扫描一遍数组,记录下每根bar左边最高的bar,然后从右向左,一遍记录当前最高的bar,一边计算每根bar上方可以盛水的量,并求和。

【Leetcode】Trapping Rain Water,布布扣,bubuko.com

【Leetcode】Trapping Rain Water

上一篇:php 微信公众号上传永久素材


下一篇:仿微信聊天界面