trapping rain water leetcode No42. Trapping Rain Water－IT工程師數位筆記本

文章出處

Question:

Givennnon-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], return6.

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 Marcosfor contributing this image!

數組元素代表高度，如圖所示，求能裝多少水

Algorithm：

分別從左右兩邊向最高點逼近，只在元素小的一邊地方儲水。由左邊向最高點逼近時，設左邊當前的最大值leftmax,當前遍歷到i，如果leftmax > A[i]; sum += (leftmax- A[i]);否則，currentMax = i，此條帶無法儲水；由右邊逼近最高點類似左邊。

Accepted Code:

class Solution {public:    int trap(vector& height) {        int left=0;           int right=height.size()-1;        int leftmax=0;   //左邊最大值        int rightmax=0;  //右邊最大值        int res=0;       //結果        while(left<=right)        {            if(height[left]<=height[right])            {                if(height[left]>leftmax)                    leftmax=height[left];                else                    res+=leftmax-height[left];                left++;            }            else            {                if(height[right]>rightmax)                    rightmax=height[right];                else                    res+=rightmax-height[right];                right--;            }        }        return res;    }};

就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161116/53967.html

文章列表