思路和时间复杂度

1. 思路：找到最左侧，比它大的元素，然后找到最右侧比它的元素，初始化了两个left和right作为当前元素左边和右边第一个比它大的元素，然后遍历时，不断寻找左右两侧的最高点，选择二者较低的减去自身高度作为高度
2. 时间复杂度：       

两个数组的建立是，然后遍历求当前雨水高度时，如果呈现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;}
};