题目描述
给定n个非负整数表示宽度为1的柱子高度,按此排序下雨后能接多少水。
image
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解题思路
每个柱子可接的水量 = min(左边柱子高度,右边柱子高度) 与当前柱子高度的差。当然最左、最右柱子不可以接水。
所以可以定义两个数组left和right,分别存储i左边柱子的最大高度、i右边柱子的最大高度。
int trap(vector<int>& height){
int length = height.size();
if(length < 1)
return 0;
vector<int> left(length, 0);
vector<Int> right(length, 0);
int max_left = height[0];
for(int i=1; i<length-1; i++){
if(max_left<height[i])
max_left = height[i];
left[i] = max_left;
}
int max_right = height[length-1];
for(int j=length-2; j>=0; j--){
if(max_right<height[j])
max_right = height[j];
right[j] = max_right;
}
int ret = 0;
for(int i=1; i<length-1; i++){
int min_height = min(left[i], right[i]);
ret += max(0, min_height-height[i]);
}
return ret;
}
更优解:双指针法,不需要设定left数组和right数组,仅保留max_left和max_right。这是因为计算每个位置的水量时,仅需要知道一边最小的高度就好。
- 当当前左边界<右边界,收集left处的水,左边界++
- 当当前左边界>有边界,收集right处的水,右边界--
int trap(vector<int>& height) {
int length = height.size();
if(length<1)
return 0;
// max_left, 当前左边最大高度;max_right,当前右边最大高度
int max_left = height[0], max_right = height[length-1];
// left,当前左边收集下标;right,当前右边收集下标
int left = 1, right = length - 2;
int ret = 0;
for(int i=1; i<length-1; i++){
if(max_left<max_right){
max_left = max(height[left], max_left);
ret += max(0, max_left - height[left]);
left++;
}else{
max_right = max(height[right], max_right);
ret += max(0, max_right - height[right]);
right--;
}
}
return ret;
}
网友评论