leetcode股票最大收益，leetcode最大矩形_柱狀圖中的最大矩形

class Solution {
public:int largestRectangleArea(vector<int>& heights) {set<int> heightSet;for(int h : heights)heightSet.insert(h);int ans = 0;for(int h_set : heightSet){int count = 0;int maxCount = 0;for(int h_s : heights){if(h_set <= h_s)count++;else{maxCount = max(maxCount,count);count = 0;}}maxCount = max(count,maxCount);ans = max(ans, maxCount * h_set);}return ans;}
};

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int len = heights.size();int ans = 0;vector<vector<int>> dp(len,vector<int>(len,0));for(int i = 0; i < len; i++){for(int j = i;j < len; j++){if(i == j || heights[j] < dp[i][j-1])dp[i][j] = heights[j];elsedp[i][j] = dp[i][j-1];ans = max(ans, (j-i+1)*dp[i][j]);}}return ans;}
};

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int len = heights.size();int ans = 0;int pre = 0;int cur = 0;for(int i = 0; i < len; i++){for(int j = i; j < len; j++){if(i ==j || heights[j] < pre){cur = heights[j];}else{cur = pre;}pre = cur;ans = max(ans, (j-i+1)*cur);}}return ans;}
};

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> s;// 最數組的最前面后最后面加上1，確保原始數組的第一個和最后一個都可以成為答案輸出出來heights.push_back(0);heights.insert(heights.begin(),0);int ans = 0;for(int i = 0; i < heights.size(); i++){// 如果當前這個數小于棧最上面的數，那么棧最上面的這個數，它的矩陣最右邊就是當前i-1，因為i是右邊第一個比它小的// 左邊的就是棧里面第二個數的索引+1，因為棧是單調增的，下面的這個數肯定小于它while(!s.empty() && heights[s.top()] > heights[i]){int index = s.top();s.pop();int left = s.top()+1;int right = i-1;ans = max(ans, (right - left + 1)* heights[index]);}s.push(i);}return ans;}
};