Trapping Rain Water

文章目录

1. 1. Trapping Rain Water
   1. 1.1. 题目
   2. 1.2. 思路
   3. 1.3. 解题

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.

思路

左右逼近，利用第二高度。

解题

c++版

class Solution {
public:
    int trap(vector<int>& height) {
        int secHight = 0;
		int left = 0;
		int right = height.size()-1;
		int area = 0;
		while (left < right){
			if (height[left] < height[right]){
				secHight = max(height[left], secHight);
				area += secHight-height[left];
				left++;
			} else {
				secHight = max(height[right], secHight);
				area += secHight-height[right];
				right--;
			}
		}
		return area;
    }
};

python版

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def trap(self, height):
        left=0
        right=len(height)-1
        secHeight=0
        area=0
        while left<right:
            if height[left]<height[right]:
                secHeight=max(height[left],secHeight)
                area+=secHeight-height[left]
                left+=1
            else:
                secHeight=max(height[right],secHeight)
                area+=secHeight-height[right]
                right-=1
        return area