算法训练第五十九天

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

代码：

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<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) return result;// 开始单调栈stack<int> st;st.push(0);for (int i = 1; i < nums.size(); i++) { if (nums[i] < nums[st.top()]) st.push(i); else if (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);return result;}
};

42. 接雨水 - 力扣（LeetCode）

代码：

class Solution {
public:int trap(vector<int>& height) {stack<int> st;st.push(0);int area = 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()]){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<int>& heights) {heights.insert(heights.begin(),0);heights.push_back(0);stack<int> st;st.push(0);int area = 0;for(int i = 1;i < heights.size();i++){if(heights[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;}
};