LeetCode 题解（14）:Trapping Rain Water

本文主要是介绍LeetCode 题解（14）: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.

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!

题解：

规律：每一个位置的储水量取决于该位置的 Left Largest Height (LLH) 和 Right Largest Height (RLH)，对于位置i，

若A[i] < min(LLH[i], RLH[i])，则该点储水量为min(LLH[i], RLH[i])-A[i]，

否则若A[i] >= min(LLH[i], RLH[i])，则该点的储水量为0。

从左至右扫描数组获得LLH[i]，从右至左边求RLH[i]边计算储水量。

需要额外O(n)存储空间，时间复杂度O(2n)=O(n)。

class Solution {
public:int trap(int A[], int n) {int* leftMaxHeight = new int[n];int leftMaxH = 0;for(int i = 0; i < n; i++){leftMaxHeight[i] = leftMaxH;if(A[i] > leftMaxH)leftMaxH = A[i];}int rightMaxH = 0;int sum = 0;for(int j = n - 1; j >= 0; j--){if(A[j] < FindMin(rightMaxH, leftMaxHeight[j]))sum += FindMin(rightMaxH, leftMaxHeight[j]) - A[j];if(A[j] > rightMaxH)rightMaxH = A[j];}return sum;}int static FindMin( int a, int b){if(a <= b)return a;else return b;}
};

这篇关于LeetCode 题解（14）:Trapping Rain Water的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---