LeetCode——Trapping Rain Water

浏览数：33 / 时间：2015年06月11日

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!

题目：给定n个非负整数代表一个宽度图，每个小格的宽度是1，计算雨后它可以保存多少雨。

原题链接：https://oj.leetcode.com/problems/trapping-rain-water/

分析：类似于木桶原理，它能存储的水取决于一个区间内最左侧的最高的一格和右侧最高的一格。所以先找到最高的点、小于最高点的左右次高点，保存左右到最高点间的水量。

	public static int trap(int[] A){
		int len = A.length;
		if(len <= 2)
			return 0;
		int higest = A[0],high_index = 0;
		for(int i=0;i<len;i++){
			int tmp = A[i];
			if(higest < tmp){
				higest = A[i];
				high_index = i;
			}
		}
		int sum = 0;
		int maxl = A[0],maxr = A[len-1];
		for(int i=0;i<high_index;i++){
			if(A[i] > maxl)
				maxl = A[i];
			else
				sum += maxl - A[i];
		}
		for(int i=len-1;i>high_index;i--){
			if(A[i] >maxr)
				maxr = A[i];
			else
				sum += maxr-A[i];
		}
		return sum;
	}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

LeetCode——Trapping Rain Water