力扣-单调栈-42-接雨水
目录
力扣-单调栈-42 接雨水
思路和时间复杂度
- 思路：找到最左侧，比它大的元素，然后找到最右侧比它的元素，初始化了两个left和right作为当前元素左边和右边第一个比它大的元素，然后遍历时，不断寻找左右两侧的最高点，选择二者较低的减去自身高度作为高度
- 时间复杂度：
两个数组的建立是
，然后遍历求当前雨水高度时，如果呈现U字形，在底部正中央需要遍历所有元素，在偏离两侧的节点中，会逐渐减少，应该是小于
代码
class Solution {
public:
int trap(vector<int>& height) {
vector<int> right(height.size(), -1);
vector<int> left(height.size(), -1);
stack<int> st;
st.push(0);
for(int i = 1; i < height.size(); i++){
if(height[i] <= height[st.top()]){
st.push(i);
}else{
while(!st.empty() && height[i] > height[st.top()]){
right[st.top()] = i;
st.pop();
}
st.push(i);
}
}
st = stack<int>();
st.push(height.size()-1);
for(int i = height.size()-2; i >= 0; i--){
if(height[i] <= height[st.top()]){
st.push(i);
}else{
while(!st.empty() && height[i] > height[st.top()]){
left[st.top()] = i;
st.pop();
}
st.push(i);
}
}
int res = 0;
for(int i = 0; i < height.size(); i++){
if(left[i] == -1 || right[i] == -1)
continue;
int leftIndex = left[i];
int rightIndex = right[i];
while (left[leftIndex] != -1)
leftIndex = left[leftIndex];
while (right[rightIndex] != -1)
rightIndex = right[rightIndex];
int curHeight = min(height[leftIndex], height[rightIndex]);
res += curHeight - height[i];
}
return res;
}
};