【Hot 100】84. 柱状图中最大的矩形

• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：【Hot 100】84. 柱状图中最大的矩形
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

引言

柱状图中最大的矩形

• 🎈 题目链接：
• 🎈 做题状态：

我的解题

下面是直接暴力解法，时间复杂度是O(n^2)

class Solution {
public:int largestRectangleArea(vector<int>& heights) {// 以当前自己为最小值，然后往左右延伸，所能形成的矩形的面积，然后算出最大的。int maxArea = -1;for (int i = 0; i < heights.size(); ++i){int curArea;// 寻找左边界int left = i - 1;while (left >= 0 && heights[left] >= heights[i]){--left;}++left;// 寻找右边界int right = i + 1;while(right < heights.size() && heights[right] >= heights[i]){++right;}--right;// 计算面积maxArea = max(maxArea, (right - left + 1) * heights[i]);}return maxArea;}
};

单调栈解法

下面是官方的单调栈解法。

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();vector<int> left(n), right(n);stack<int> mono_stack;for (int i = 0; i < n; ++i) {while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {mono_stack.pop();}left[i] = (mono_stack.empty() ? -1 : mono_stack.top());mono_stack.push(i);}mono_stack = stack<int>();for (int i = n - 1; i >= 0; --i) {while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {mono_stack.pop();}right[i] = (mono_stack.empty() ? n : mono_stack.top());mono_stack.push(i);}int ans = 0;for (int i = 0; i < n; ++i) {ans = max(ans, (right[i] - left[i] - 1) * heights[i]);}return ans;}
};