题目主要信息:
- 给定一个整型数组,数组每个元素表示下图所示的每列灰色柱子高度,数值都是非负数
- 在雨水(图中蓝色部分)不超过边界的情况下,问最多能有多少蓝色的格子
- 数组以外的区域高度视为0
举一反三:
方法:双指针(推荐使用)
知识点:双指针
双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个指针(特殊情况甚至可以多个),两个指针或是同方向访问两个链表、或是同方向访问一个链表(快慢指针)、或是相反方向扫描(对撞指针),从而达到我们需要的目的。
思路:
我们都知道水桶的短板问题,控制水桶水量的是最短的一条板子。这道题也是类似,我们可以将整个图看成一个水桶,两边就是水桶的板,中间比较低的部分就是水桶的底,由较短的边控制水桶的最高水量。但是水桶中可能出现更高的边,比如上图第四列,它比水桶边还要高,那这种情况下它是不是将一个水桶分割成了两个水桶,而中间的那条边就是两个水桶的边。
有了这个思想,解决这道题就容易了,因为我们这里的水桶有两个边,因此可以考虑使用对撞双指针往中间靠。
具体做法:
- step 1:检查数组是否为空的特殊情况
- step 2:准备双指针,分别指向数组首尾元素,代表最初的两个边界
- step 3:指针往中间遍历,遇到更低柱子就是底,用较短的边界减去底就是这一列的接水量,遇到更高的柱子就是新的边界,更新边界大小。
图示:
Java代码实现:
import java.util.*;
public class Solution {
public long maxWater (int[] arr) {
//排除空数组
if(arr.length == 0)
return 0;
long res = 0;
//左右双指针
int left = 0;
int right = arr.length - 1;
//中间区域的边界高度
int maxL = 0;
int maxR = 0;
//直到左右指针相遇
while(left < right){
//每次维护往中间的最大边界
maxL = Math.max(maxL, arr[left]);
maxR = Math.max(maxR, arr[right]);
//较短的边界确定该格子的水量
if(maxR > maxL)
res += maxL - arr[left++];
else
res += maxR - arr[right--];
}
return res;
}
}
C++代码实现:
class Solution {
public:
long long maxWater(vector<int>& arr) {
//排除空数组
if(arr.size() == 0)
return 0;
long long res = 0;
//左右双指针
int left = 0;
int right = arr.size() - 1;
//中间区域的边界高度
int maxL = 0;
int maxR = 0;
//直到左右指针相遇
while(left < right){
//每次维护往中间的最大边界
maxL = max(maxL, arr[left]);
maxR = max(maxR, arr[right]);
//较短的边界确定该格子的水量
if(maxR > maxL)
res += maxL - arr[left++];
else
res += maxR - arr[right--];
}
return res;
}
};
Python实现代码:
class Solution:
def maxWater(self , arr: List[int]) -> int:
#排除空数组
if len(arr) == 0:
return 0
res = 0
#左右双指针
left = 0
right = len(arr) - 1
#中间区域的边界高度
maxL = 0
maxR = 0
#直到左右指针相遇
while left < right:
#每次维护往中间的最大边界
maxL = max(maxL, arr[left])
maxR = max(maxR, arr[right])
#较短的边界确定该格子的水量
if maxR > maxL:
res += maxL - arr[left]
left += 1
else:
res += maxR - arr[right]
right -= 1
return res
复杂度分析:
- 时间复杂度:,两个指针最多共同遍历整个数组
- 空间复杂度:,常数个变量,没有额外的辅助空间