接雨水问题

接雨水问题

读前福利，送大家一些电子书

42. 接雨水

问题描述

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

示例：

输入：height = [4,2,0,3,2,5]

输出：9

解释：上面是由数组 [4,2,0,3,2,5] 表示的高度图，在这种情况下，可以接 9 个单位的雨水（蓝色部分表示雨水）。

分析问题

我们最直观的想法就是，对于数组中的每个元素，下雨后能存水的高度等于它两边最大高度的较小值减去当前高度的值。比如对于数组中第二个元素，它能储水的高度就是min(maxleft,maxright)-height[1]=4-2=2。

对于求它两边的最大高度，我们可以以当前元素为基准，分别进行向左和向右扫描来求得。

下面我们来看一下代码实现。

def result(height):
    ans=0
    n=len(height)
    for i in range(1,n):
        maxleft=0
        maxright=0
        
        ##向左扫描
        for j in range(i, -1, -1):
            maxleft=max(maxleft,height[j])

        ##向右扫描
        for j in range(i,n):
            maxright=max(maxright,height[j])

        ans=ans+min(maxleft,maxright)-height[i]

    return ans

height=[4,2,0,3,2,5]
print(result(height))

我们可以很明显的看到，对于数组中的每一个元素，我们都需要向左和向右进行扫描，所以这个算法的时间复杂度为O(n^2)。

优化

我们可以发现在上个算法中，我们对于数组中的每个元素都需要花费O(n)的时间去向左和向右扫描，去寻找两边的最大值。如果我们可以提前知道每个位置对应的两边的最大高度，则可以在O(n)的时间内去求得雨水的总量。

下面我们来看一下如何通过预处理来得到每个元素对应的两边的最大高度。

我们先来看一下如何求每个位置对应的左边的最大高度，对于元素height[i]来说，leftmax要么是它本身，要么是heght[i-1]对应的leftmax的值，即leftmax[i]=max(leftmax[i-1]，height[i])，其中**leftmax[i]**表示下标i及其左边的位置中，height的最大高度。

同理可以求得，rightmax[i]=max(rightmax[i+1]，height[i])，其中**rightmax[i]**表示下标i及其右边的位置中，height的最大高度。

下面我们来看一下代码如何实现。

def result(height):
    if not height:
        return

    n=len(height)
    ##求出左边最大
    leftmax=[0]*n
    leftmax[0]=height[0]
    for i in range(1,n):
        leftmax[i]=max(leftmax[i-1],height[i])

    rightmax=[0]*n
    rightmax[n-1]=height[n-1]
    for i in range(n-2,-1,-1):
        rightmax[i]=max(rightmax[i+1],height[i])

    ans = 0
    for i in range(0,n):
       ans=ans+min(leftmax[i],rightmax[i])-height[i]
    return ans

height=[4,2,0,3,2,5]
print(result(height))

通过代码，我们可以清楚的知道，这个算法的时间复杂度为O(n)，空间复杂度也为O(n)。

终极解法

在优化算法中，我们引入了两个数组leftMax和rightMax来保存每个位置对应的两边的最大高度，因此空间复杂度为O(n)，那我们有什么方法可以来降低空间复杂度吗？

我们可以观察到，对于下标i处能接的雨水量是由leftMax[i]和rightMax[i]中的最小值决定。由于数组leftMax是从左往右计算，而数组rightMax是从右往左计算，所以我们可以使用双指针和两个变量来替代这两个数组，下面我们来看一下。

我们维护两个指针left和right，以及两个变量leftMax和rightMax，初始时left=0，right=n-1，leftMax=0，rightMax=0。指针left只能往右移动，指针right只能往左移动，然后在移动的过程中，去更新变量leftMax和rightMax的值。

在开始阶段left=0，right=n-1，leftMax=0，rightMax=0。然后**height[left]和height[right]**进行比较。这时会出现两种情况：

1.如果此时height[left]<height[right]，则leftMax=max(leftMax,height[left])=height[left]<height[right]=rightMax，所以下标left处能接的雨水量为leftMax-height[left]，然后left往右移动一位，此时left=left+1=1。

2.如果此时height[left]>=height[right]，则leftMax=max(leftMax,height[left])=height[left]>=height[right]=rightMax，所以下标right处能接的雨水量位rightMax-height[right]，然后right往左移动一位，此时right=right-1=n-2。

然后循环执行1，2步，直到left和right相遇为止。

下面我们来总结一下，在指针left和right没有相遇时，我们执行如下操作。

1.使用height[left]和height[right]来更新leftMax和rightMax。

2.如果height[left]<height[right]，则必有leftMax<rightMax。下标left处能接的雨水量为leftMax-height[left]，然后left往右移动一位。

3.如果height[left]>=height[right]，则必有leftMax>=rightMax。下标right处能接的雨水量为rightMax-height[right]，然后right往左移动一位。

下面我们来看一下代码的实现。

def result(height):
    if not height:
        return

    n=len(height)

    left=0
    leftMax=0
    right=n-1
    rightMax=0

    ans = 0
    while left < right:
        leftMax=max(leftMax,height[left])
        rightMax=max(rightMax,height[right])

        if height[left] < height[right]:
            ans=ans+leftMax-height[left]
            left=left+1
        else:
            ans=ans+rightMax-height[right]
            right=right-1

    return ans

height=[4,2,0,3,2,5]
print(result(height))

我们通过分析代码可以很容易的知道，这个算法的时间复杂度是O(n)，空间复杂度为O(1)。