问题
给定一个非负数的数组,代表一个容器。例如数组[0,1,0,2,1,0,1,3,2,1,2,1],就是 以下图形中黑色的部分。如果用这个容器接水的话,请问可以接多少水?还以这个数组为例,
可以接 6 格水,就是以下图形中蓝色的部分。 要求:实现时间复杂度 O(N),额外空间复杂度 O(1)的解法
思路
解法1
设第i个位置上的储水量w[i],故容量总储水量为各位置的储水之和。
w[i]的计算方法,根据储水特点,短板原理,即i位置左侧最大值lmax与右侧最大值rmax中较小的一侧决定该位置的储水能力。
w[i] = MAX{0, MIN(lmax, rmax) - arr[i]};
实现过程中,需注意的两个小地方
- 各位置最大值之前,
先初始化lmax,rmax
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),简直精彩