本文共 1508 字，大约阅读时间需要 5 分钟。

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.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6

分析

给出一个包含n个非负整数的数组，表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

需要两边的柱子高度大于中间的柱子高度才能存住水。因此我们可以从左到右进行遍历。

• 如果找得到，计算这中间可以存放多少水；然后从找到的柱子继续遍历。
• 如果找不到，则找出剩下柱子最高的那根柱子，计算这中间可以存放多少水，然后从找到的柱子继续遍历。
• 如果当前柱子高度为0，则从下一根柱子开始遍历。

使用该方法，平均时间复杂度为$O(n)$，最差时间复杂度为$O(n^2)$。

代码如下

class Solution {
       public int trap(int[] height) {
       	if (height.length <= 2) {
     // 数组长度至少为3才可以装水    		return 0;    	}    	    	int i = 0;    	int sum = 0;    	while (i < height.length - 1) {
   			if (height[i] == 0) {
   				i++;			} else {
   				// 寻找下一个大于等于当前值的下标（找不到则找最大的）				int greaterOrMax = 0;				int j;				int index = -1;				for (j = i + 1; j < height.length; j++) {
   					if (height[j] >= height[i]) {
     // 大于等于当前值						index = j;						greaterOrMax = height[i];  // 只能取值为height[i]						break;					} else if (height[j] > greaterOrMax) {
     // 大于最大值						greaterOrMax = height[j];						index = j;					}				}				for (int k = i + 1; k < index; k++) {
   					sum += (greaterOrMax - height[k]);				}				if (index > 0) {
   					i = index;				} else {
   					i++;				}			}		}		return sum;    }}

转载地址：http://dibmb.baihongyu.com/