[刷题]Leetcode.42 接雨水
文章目录
传送门
题目描述:
一道困难题,看题解的时候说面试经常问,就记录一下这一题。
图中黑色的代表柱子,蓝色的代表水,最终求解蓝色的面积。
这道题从整体去考虑,没有思路。
看了题解(传送门)说要单个单个考虑,是从列来看的。
对于单个列来说
这个列能存的雨水 = MIN( 这个列左边的最高高度,这个列右边的最低高度 ) - 这个列的高度
当然 最低只能为0
找到这个规律 是解这道题的关键, 可以结合图理解这个规律
那么解法也很容易想到了
对每一位置,我们找到这个位置左边的最高高度和这个位置右边的最高高度,然后按规律计算即可。
我们可以用一个数组保存每个位置左边的最高高度,从左往右遍历;求右边最高高度,从右往左同理;
代码如下:
public int trap(int[] height) {
if(height.length<2) return 0;
int[] l_max = new int[height.length];
int[] r_max = new int[height.length];
l_max[0] = height[0];
r_max[height.length-1] = height[height.length-1];
for(int i=1;i<height.length;i++){
l_max[i] = Math.max(l_max[i-1], height[i]);
}
for(int i=height.length-2;i>=0;i--){
r_max[i] = Math.max(r_max[i+1],height[i]);
}
int ans = 0;
for (int i=0;i<height.length;i++){
ans += Math.max ((Math.min(l_max[i],r_max[i])-height[i]),0);
}
return ans;
}
只有三次从头到尾的遍历,因此时间复杂度O(N);用了两个辅助数组,空间复杂度O(N)。
但空间复杂度可以进一步压缩为O(1)
我们用两个指针left,right分别指向左边的柱子和右边的柱子,并记录此时[0,...,left]的最高高度,我们记为l_max, [right,...,N]的最高高度,我们记为r_max。
在遍历的某个时刻,我们比较l_max,r_max,假如l_max<r_max 那么我们可以知道left左侧的最高高度为l_max,右侧的最高高度我们不能确定,但结合上面所说的规律,这足以计算left位置处的雨水面积了,因为我们取左侧最高和右侧最高中的小的那个,而此时l_max<r_max,我们使用l_max就足够了。
而当r_max<=l_max 时同理;
这样,我们不需要用辅助数组,只需要两个变量即可,代码如下:
public int trap(int[] height) {
if(height.length<2) return 0;
int left = 0;
int right = height.length-1;
int l_max = 0;
int r_max = 0;
int ans = 0;
while(left<right){
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
if(l_max<r_max){
ans += (l_max-height[left]);
left++;
}
else{
ans += (r_max-height[right]);
right--;
}
}
return ans;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论