题目链接
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出： 6
解释： 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入： height = [4,2,0,3,2,5]
输出： 9
解题思路
方法一：暴力法(将每个位置假设为低洼处)
直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
- 初始化 ans=0
- 从左向右扫描数组：
- 初始化 max_left=0 和 max_right=0
- 从当前元素向左扫描并更新：max_left=max(max_left,height[j])
- 从当前元素向右扫描并更新：max_right=max(max_right,height[j])
将min(max_left,max_right)−height[i] 累加到 ans
int trap(vector<int>& height){int ans = 0;int size = height.size();for (int i = 1; i < size - 1; i++) {int max_left = 0, max_right = 0;for (int j = i; j >= 0; j--) { //Search the left part for max bar sizemax_left = max(max_left, height[j]);}for (int j = i; j < size; j++) { //Search the right part for max bar sizemax_right = max(max_right, height[j]);}ans += min(max_left, max_right) - height[i];}return ans;}
时间复杂度 O(n^2)
-
方法二：动态规划
在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此，可以通过动态编程解决。
这个概念可以见下图解释：
找到数组中从下标 i 到最左端最高的条形块高度 left_max。找到数组中从下标 i 到最右端最高的条形块高度 right_max。
- 扫描数组 height 并更新答案：
累加min(max_left[i],max_right[i])−height[i] 到 ans 上
class Solution {public:int trap(vector<int>& height) {int ans = 0;int sz = height.size();vector<int> max_left(sz),max_right(sz);max_left[0] = height[0];max_right[sz-1] = height[sz-1];for(int i=sz-2;i>=0;i--){max_right[i] = max(max_right[i+1],height[i]);}for(int i=1;i<sz-1;i++){max_left[i] = max(max_left[i-1],height[i]);ans += min(max_left[i],max_right[i]) - height[i];}return ans;}};
class Solution { public int trap(int[] height) { if(height.length < 3){ return 0; } int ans = 0; int[] max_left = new int[height.length]; // 用于记录当前位置左边的最高柱 int max_height = 0; // 记录当前最高柱 for(int i = 0; i < height.length; ++i){ max_left[i] = Math.max(height[i], max_height); max_height = Math.max(max_height, max_left[i]); } max_height = 0; // 清零 // 从右向左遍历 for(int i = height.length - 1; i > 0; --i){ max_height = Math.max(max_height, height[i]); // 用于记录当前位置右边的最高柱 ans += Math.min(max_left[i], max_height) - height[i]; // 加上当前位置雨水， 左右最高柱的最小值减去当前柱高 } return ans; } }时间复杂度 O(n)
-
方法三：栈的应用（相当于中间低洼部分一层层计算）
我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此我们可以弹出栈顶元素并且累加答案到ans 。 使用栈来存储条形块的索引下标。
- 遍历数组：
- 当栈非空且 height[current]>height[st.top()]
- 意味着栈中元素可以被弹出。弹出栈顶元素 top。
- 计算当前元素和栈顶元素的距离，准备进行填充操作 distance=current−st.top()−1
- 找出界定高度 bounded_height=min(height[current],height[st.top()])−height[top]
- 往答案中累加积水量 ans+=distance×bounded_height
- 将当前索引下标入栈
- 将 current 移动到下个位置
class Solution {
public:
int trap(vector<int>& height) {
int size = height.size();
if(size<2)
return 0;
int ans = 0;
stack<int> st;
for(int i=0;i<size;++i){
while(!st.empty()&&height[st.top()]<height[i]){
// 当前top位置为洼地,可以存水
int top = st.top();
st.pop();
if(st.empty())
break;
// 求出积水的宽
int distance = i - st.top() - 1;
// 求出积水的高
int bounded_height = min(height[i], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(i);
}
return ans;
}
};
class Solution {
public int trap(int[] height) {
if(height.length < 3){
return 0;
}
int ans = 0;
Deque<Integer> stack = new LinkedList();
for(int i = 0; i < height.length; ++i){
while(!stack.isEmpty() && height[stack.peekFirst()] < height[i]){
// 当前top位置为洼地,可以存水
int top = stack.pollFirst();
if(stack.isEmpty()){
break;
}
// 求出积水的宽
int distance = i - stack.peekFirst() - 1;
// 求出积水的高
int bounded_height = Math.min(height[i], height[stack.peekFirst()]) - height[top];
ans += distance * bounded_height;
}
stack.offerFirst(i);
}
return ans;
}
}
- 时间复杂度 O(n)
-
方法四：双指针（*）
int trap(vector<int>& height) { int left = 0, right = height.size() - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { // 这里保证了未移动的指针指向的是当前所以遍历过的数据最大值 // 接水高度由左边最大值决定 // left之前的数字肯定都小于height[right] if (height[left] < height[right]) { // 如果左边当前值大于左边最大值，则不能接水 height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]); ++left; }// 接水高度由右边最大值决定 else { // right之后的数字肯定都小于等于height[left] height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]); --right; } } return ans; }class Solution { public int trap(int[] height) { int left = 0, right = height.length - 1; int ans = 0; int max_left = 0, max_right = 0; // 左右边的最高柱子 while(left < right){ if(height[left] < height[right]){ if(height[left] >= max_left){ // 更新最高柱子，表示更左边的柱子对后面的水没有阻隔作用 max_left = height[left]; }else{ ans += (max_left - height[left]); // 加上当前列的存水量 } ++left; //前移 }else{ if(height[right] >= max_right){// 更新最高柱子，表示更右边的柱子对后面的水没有阻隔作用 max_right = height[right]; }else{ ans += (max_right - height[right]); // 加上当前列的存水量 } --right; // 后移 } } return ans; } } 时间复杂度 O(n)
- 空间复杂度 O(1)
若有收获，就点个赞吧
0 人点赞
