leetcode link: 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
1 个人思路
个人思路（快慢指针）：
- 1 slow指针用于寻找非0低的柱子，fast寻找slow右侧第一个更大柱子。
- 2 slow和fast中间的面积-slow和fast中间的柱子面积即为雨水面积。
- 3 进行从左到右，和从右到左两次计算。
class Solution {
public:
int find_next(vector& height, int slow){
for(int i=slow+1; i<height.size(); i++){ if (height[i] >= height[slow]) return i;
}
return -1;
}
int go(vector &height){
int total = 0;
int fast;
for (int slow = 0; slow < height.size() - 1; slow++) {
if (height[slow]) {
fast = find_next(height, slow);
cout << "slow is " << slow << " fast is " << fast << endl;
if (fast != -1) {
// 加上中间全部的面积
total += (fast - slow - 1) * min(height[slow], height[fast]);
// 减去中间突出块的面积
for (int j = slow + 1; j < fast; j++) {
total -= height[j];
}
cout << "total is " << total << endl;
slow = fast - 1;
}
}
}
return total;
}
int trap(vector &height) {
int front_total = 0, back_total =0, total = 0;
front_total = go(height);
reverse(height.begin(), height.end());
back_total = go(height);
total = max(front_total, back_total);
return total;
}
};
官方题解：暴力解法、双指针优化、单调栈。
2 暴力解法
暴力解法步骤：- 为1~(size-1)的元素寻找其左右两边最大的元素，然后计算面积
-
寻找i左边最大的元素
-
寻找i右边最大的元素
-
计算面积
int trap(vector &height) {
// 1 暴力解法,为1~(size-1)的元素寻找其左右两边最大的元素，然后计算面积
int total = 0;
for(int i=1; i left) left = height[j];
}
// 2 寻找i右边最大的元素
int right = height[i];
for(int j=i+1; j right) right = height[j];
}
// 3 计算面积
int h = min(left, right) - height[i];
if (h > 0) total += h;
}
return total; 3 双指针优化
双指针本质上和暴力解法差不多，但是既然暴力解法每次都需要计算i左边的最大值元素和i右边的最大值元素，那为何不使用数组存起来。
- 1 从1到i计算i左边最大值
- 2 从size()-1到i计算右边最大值
- 3 列上计算面积
Notes：
- 1 left和right数组初始化
- 2 left和right数组的遍历顺序
- 3 列上计算雨水面积
int trap(vector &height) {
int total = 0;
// 1 计算i左边最大值和右边最大值数组
vector left = height;
vector right = height;
for(int i=1; i<height.size()-1; i++){ left[i] = max(left[i], left[i-1]); } for(int i=height.size()-2; i>=1; i--) {
right[i] = max(right[i], right[i+1]);
}
// 2 计算面积
for(int j=1; j<height.size()-1; j++){ int h = min(left[j], right[j]) - height[j]; if (h > 0) total += h;
}
return total;
}4 单调栈
该题需要寻找元素i的左边最大值和右边最大值，自然想到可以使用单调栈。 假设使用单调栈寻找右边更大元素，则单调栈内元素天然有序，从栈底到栈顶的顺序为越来越小，则我们只要找到右边大于栈顶的元素（模式为大小大），即可计算雨水面积。 Notes：- 1 需要注意当输入元素与栈顶元素相等时，先弹栈，再进栈
class Solution {
public:
int trap(vector &height) {
int total = 0;
stack st;
st.push(0);
for(int i=1; i<height.size(); i++){
if(height[i] == height[st.top()]){
st.pop();
st.push(i);
}
else if (height[i] < height[st.top()]){ st.push(i); }else{ while(!st.empty() && height[i] > height[st.top()]){
int middle = st.top(); st.pop();
if (!st.empty()){
int h = min(height[st.top()], height[i]) - height[middle];
int w = i - st.top() - 1;
int sum = h * w;
if (sum > 0) total += sum;
}
}
st.push(i);
}
}
return total;
}
};