代码随想录算法训练营第六十二天|503.下一个更大元素II、42. 接雨水

503.下一个更大元素II 

两个nums数组拼接在一起，使用单调栈计算出每一个元素的下一个最大值，最后再把结果集即result数组resize到原数组大小就可以

vector<int>nextGreaterElements(vector<int>&nums){// 拼接一个新的numsvector<int>nums1(nums.begin(),nums.end());nums.insert(nums.end(),nums1.begin(),nums1.end());// 用新的nums大小来初始化resultvector<int>result(nums.size(),-1);if(nums.size()==0)returnresult;// 开始单调栈stack<int>st;st.push(0);for(inti=1;i<nums.size();i++){if(nums[i]<nums[st.top()])st.push(i);elseif(nums[i]==nums[st.top()])st.push(i);else{while(!st.empty()&&nums[i]>nums[st.top()]){result[st.top()]=nums[i];st.pop();}st.push(i);}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size()/2);returnresult;}

42. 接雨水

三种情况

情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]

if (height[i] < height[st.top()]) st.push(i);

情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]

if (height[i] == height[st.top()]) { // 例如 5 5 1 7 这种情况

  st.pop();

  st.push(i);

}

情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]

int h = min(height[st.top()], height[i]) - height[mid];

inttrap(vector<int>&height){stack<int>st;st.push(0);intsum=0;for(inti=1;i<height.size();i++){while(!st.empty()&&height[i]>height[st.top()]){intmid=st.top();st.pop();if(!st.empty()){inth=min(height[st.top()],height[i])-height[mid];intw=i-st.top()-1;sum+=h*w;}}st.push(i);}returnsum;}