首页 > 代码库 > LeetCode OJ-- Trapping Rain Water*

LeetCode OJ-- Trapping Rain Water*

https://oj.leetcode.com/problems/trapping-rain-water/

模拟题,计算出在凹凸处存水量。

对于一个位置 i ,分别计算出它左边的最大值 left (从左扫描一遍), 右边的最大值 right(从右扫描一遍) 。找left right中的最小值,如果大于 A[i],则做 min - A[i] 的累加。

class Solution {public:    int trap(int A[], int n) {        if(n<=1)            return 0;        vector<int> leftHigher;        vector<int> rightHigher;        int leftLarge = 0, rightLarge = 0;        for(int i = 0;i<n;i++)        {            if(A[i]>leftLarge)                leftLarge = A[i];            leftHigher.push_back(leftLarge);        }        rightHigher.resize(n);        for(int j = n-1;j>=0;j--)        {            if(A[j]>rightLarge)                rightLarge = A[j];            rightHigher[j] = rightLarge;        }        int sum = 0;        for(int i = 0;i<n;i++)        {            int min = leftHigher[i]<rightHigher[i]?leftHigher[i]:rightHigher[i];            if(min>A[i])                sum += min - A[i];        }                return sum;    }};