LeetCode:Trapping Rain Water
1733 ワード
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
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!
For example, Given
[0,1,0,2,1,0,1,3,2,1,2,1]
, return 6
. 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!
// https://oj.leetcode.com/problems/trapping-rain-water/
// Author : Chao Zeng
// Date : 2015-2-11
class Solution {
public:
int trap(int A[], int n) {
int ans = 0;
int maxnum = A[0];
int flag = 0;
for (int i = 0; i < n; i++){
if (maxnum < A[i]){
maxnum = A[i];
flag = i;
}
}
int currentmaxnum = A[0];
for (int i = 0; i < flag ; i++){
if (currentmaxnum < A[i]){
currentmaxnum = A[i];
}
if (A[i] < maxnum && A[i] < currentmaxnum){
ans += currentmaxnum - A[i];
}
}
currentmaxnum = A[n - 1];
for (int i = n -1; i > flag; i--){
if (currentmaxnum < A[i]){
currentmaxnum = A[i];
}
if (A[i] < maxnum && A[i] < currentmaxnum){
ans += currentmaxnum - A[i];
}
}
return ans;
}
};