算法训练第五十九天

503. 下一个更大元素 II – 力扣（LeetCode）

代码：

class Solution {public:vector nextGreaterElements(vector& nums) {vector nums1(nums.begin(), nums.end());nums.insert(nums.end(), nums1.begin(), nums1.end());// 用新的nums大小来初始化resultvector result(nums.size(), -1);if (nums.size() == 0) return result;// 开始单调栈stack st;st.push(0);for (int i = 1; i < nums.size(); i++) { if (nums[i]  nums[st.top()]) {result[st.top()] = nums[i];st.pop();}st.push(i);}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size() / 2);return result;}};

42. 接雨水 – 力扣（LeetCode）

代码：

class Solution {public:int trap(vector& height) {stack st;st.push(0);int area = 0;for(int i = 1;i < height.size();i++){if(height[i]  height[st.top()]){int mid = st.top();st.pop();if(!st.empty()){int h = min(height[i],height[st.top()]) - height[mid];int w = i - st.top() - 1;area += h * w;}}st.push(i);}}return area;}};

84. 柱状图中最大的矩形 – 力扣（LeetCode）

代码：

class Solution {public:int largestRectangleArea(vector& heights) {heights.insert(heights.begin(),0);heights.push_back(0);stack st;st.push(0);int area = 0;for(int i = 1;i = heights[st.top()])st.push(i);else{while(!st.empty() && heights[i] < heights[st.top()]){int mid = st.top();st.pop();if(!st.empty()){int h = heights[mid];int w = i - st.top() - 1;area = max(area,h * w);}}st.push(i);}}return area;}};