算法训练第五十九天

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大小来初始化result vector<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; } };