容器盛水问题

发表于 | 分类于 |

问题

给定一个非负数的数组,代表一个容器。例如数组[0,1,0,2,1,0,1,3,2,1,2,1],就是 以下图形中黑色的部分。如果用这个容器接水的话,请问可以接多少水?还以这个数组为例,
可以接 6 格水,就是以下图形中蓝色的部分。 要求:实现时间复杂度 O(N),额外空间复杂度 O(1)的解法

如图所示
water

思路

解法1

设第i个位置上的储水量w[i]，故容量总储水量为各位置的储水之和。
w[i]的计算方法，根据储水特点，短板原理，即i位置左侧最大值lmax与右侧最大值rmax中较小的一侧决定该位置的储水能力。

w[i] = MAX{0, MIN(lmax, rmax) - arr[i]};

实现过程中，需注意的两个小地方

  1. 各位置最大值之前，先初始化lmax，rmax
  2. for (int i = 1; i < length - 1; i++)i的遍历范围

核心代码

int getWater1(int *arr)
{
    //边界条件
    if (arr == NULL || length < 3)
    {
        return 0;
    }

    int value = 0;

    for (int i = 1; i < length - 1; i++)
    {
        //计算各位置最大值之前，先初始化lmax，rmax
        int lmax = 0;
        int rmax = 0;
        for (int l = 0; l < i; l++)
        {
            lmax = max(lmax ,arr[l]);
        }
        for (int r = length - 1; i < r; r--)
        {
            rmax = max(rmax ,arr[r]);
        }
        w[i] = max(0, min(lmax, rmax) - arr[i]);
        value += w[i];
    }
    return value;
}

枚举计算w[i],再求和。此时的时间复杂度为⊖(n^2)

解法2

优化解法1中对每个位置的左右两侧最大值的计算。以空间换时间，利用
Left数组，Right数组分别记录每个位置左侧和右侧的最大值
核心代码

int getWater2(int *arr)
{
    //边界条件
    if (arr == NULL || length < 3)
    {
        return 0;
    }

    int value = 0;

    int lmax = arr[0];
    int rmax = arr[length - 1];
    int Left[length];
    int right[length];
    for (int l = 1; l < length; l++)
    {
        lmax = max(lmax ,arr[l]);
        Left[l] = lmax;
    }
    for (int r = length - 2; r >= 0; r--)
    {
        rmax = max(rmax ,arr[r]);
        right[r] = rmax;
    }
    for (int i = 1; i < length - 1; i++)
    {
        w[i] = max(0, min(Left[i], right[i]) - arr[i]);
        value += w[i];
    }
    return value;
}

优化后的时间复杂度降为⊖(n)

解法3

优化解法2，干掉Left数组，由于遍历的过程为从左到右，我们仅需一个Lmax变量记录当前最大即可完成Left数组的功能。
部分代码

int getWater3(int *arr)
{
    for (int i = 1; i < length - 1; i++)
    {
        lmax = max(lmax ,arr[i]);
        w[i] = max(0, min(lmax, right[i]) - arr[i]);
        value += w[i];
    }
    return value;
}

相比解法2，在空间上得到优化，只要到一个数组。时间复杂度仍为⊖(n)

解法4

这里要介绍一个强大的解题利器，双指针。4个变量立即解决问题（服不服！
现在先介绍各变量的含义:l, lmax, r, rmax
l: 左侧工作指针 lmax: 保存i位置左侧最大值
r: 右侧工作指针 rmax: 保存j位置右侧最大值

算法流程介绍说明：
arr数组部分值:...5 4 6 8....3 7...
我们来看看左侧工作指针是如何工作的。假设现在l 指向 4, r 指向 3, lmax = 5, rmax = 7;此时arr值为4的位置处储水量可以确定下来，即使目前其右侧还未访问到，不知道它们的值。但是由于rmax为7,则4的位置右侧已经出现大于lmax的值了。由短板原理可得，4位置处的储水量为5 - 4 = 1。l向右移动一位，四个变量的值l 指向 6, r 指向 3, lmax = 5, rmax = 7

当l 指向 8时，工作原理同上，3位置处的出水量可以确定，其值为7 - 3 =4，r向左移动。左右工作指针相遇即循环结束，遍历完成
部分代码

int getWater4(int *arr)
{
    int value = 0;
    int l = 1; int r = length - 2;
    int lmax = arr[0]; int rmax = arr[length - 1];

    while (l <= r)
    {
        if (lmax <= rmax)
        {
            value += max(0, lmax - arr[l]);
            //更新lmax后再右移
            lmax = max(lmax, arr[l++]); 
        }
        else
        {
            value += max(0, rmax - arr[r]);
            //更新rmax后再左移
            rmax = max(rmax, arr[r--]);
        }
    }
    return value;
}

小提醒arr[l++]先取值，再自加
时间复杂度⊖(n)，空间复杂度⊖(1)，简直精彩