503.下一個更大元素II?

兩個nums數(shù)組拼接在一起，使用單調(diào)棧計算出每一個元素的下一個最大值，最后再把結(jié)果集即result數(shù)組resize到原數(shù)組大小就可以

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;// 開始單調(diào)棧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);}}// 最后再把結(jié)果集即result數(shù)組resize到原數(shù)組大小result.resize(nums.size()/2);returnresult;}

42.?接雨水

三種情況

情況一：當(dāng)前遍歷的元素（柱子）高度小于棧頂元素的高度 height[i] < height[st.top()]

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

情況二：當(dāng)前遍歷的元素（柱子）高度等于棧頂元素的高度 height[i] == height[st.top()]

if (height[i] == height[st.top()]) { // 例如 5 5 1 7 這種情況

? st.pop();

? st.push(i);

}

情況三：當(dāng)前遍歷的元素（柱子）高度大于棧頂元素的高度 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;}