本文主要是介绍Day60 单调栈part03 84. 柱状图中最大的矩形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Day60 单调栈part03 84. 柱状图中最大的矩形
84. 柱状图中最大的矩形
暴力法
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int sum = 0;for (int i = 0; i < heights.size(); i++) {int left = i;int right = i;for (; left >= 0; left--) {if (heights[left] < heights[i]) break;}for (; right < heights.size(); right++) {if (heights[right] < heights[i]) break;}int w = right - left - 1;int h = heights[i];sum = max(sum, w * h);}return sum;}
};
单调栈
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0; //记录结果stack<int> stk;heights.insert(heights.begin(),0); //头部添加元素0heights.push_back(0); //尾部添加元素0stk.push(0);for(int i = 1;i<heights.size();i++){if(heights[i] >= heights[stk.top()]) stk.push(i);else{while(!stk.empty()&&heights[i] < heights[stk.top()]){int mid = stk.top();stk.pop();if(!stk.empty()){int height = heights[mid];int width = i - stk.top()-1;result = max(result,height*width);}}stk.push(i);}}return result;}
};
这篇关于Day60 单调栈part03 84. 柱状图中最大的矩形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
