首页 > 代码库 > 【leetcode】Trapping Rain Water

【leetcode】Trapping Rain Water

2024-07-12 16:35:15   216人阅读

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!

 

题解：在网上研究了半天，才找到时间O(n)和空间O(1)的算法：

  1. 首先找出最大的bar，索引记录在totalMaxIndex这个变量里面；
  2. 从左往右，依次处理totalMaxIndex左边的bar；设置一个curMax记录遍历到当前为止最大的bar，那么对于A[i]，有两种可能：一是A[i]<curMax，那么这时候就可以储水(curMax - A[i])；而是A[i] > curMax，这时更新curMax = A[i]；
  3. 从右往左，依次处理totalMaxIndex右边的bar，方法同2.

具体算法过程如下图所示：

基本的原理就是当从左往右遍历的时候，最高的bar保证了能够在右端将水拦住，那么就只要计算对于A[i]，在左端能够拦截住多高的水就可以了，即变量curMax。

代码如下：

 1 public class Solution { 2     public int trap(int[] A) { 3         if(A == null || A.length == 0) 4             return 0; 5          6         int curMax = 0; 7         int totalMax = A[0]; 8         int totalMaxIndex = 0; 9         int answer = 0;10         11         for(int i = 1;i < A.length;i++){12             if(A[i] > totalMax){13                 totalMax = A[i];14                 totalMaxIndex = i;15             }16         }17         18         for(int i = 0;i < totalMaxIndex;i++){19             if(A[i] < curMax)20                 answer += curMax - A[i];21             else22                 curMax = A[i];23         }24         25         curMax = 0;26         for(int i = A.length-1;i > totalMaxIndex;i--){27             if(A[i] < curMax)28                 answer += curMax - A[i];29             else {30                 curMax = A[i];31             }32         }33         34         return answer;35     }36 }


联系
我们