• 困难
• 中等
• 简单

  题目描述

  给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
  求在该柱状图中，能够勾勒出来的矩形的最大面积。
  
  以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
  
  图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

来源，leetcode 每日一题 84. 柱状图中最大的矩形

例如：

输入: [2,1,5,6,2,3]
输出: 10

解题思路

1. 暴力方法：以每个柱子为左边界，向右边探查可围成的最大矩形面积。

   class Solution {
   public:
    int largestRectangleArea(vector<int>& heights) {
        int s = 0;
        for (int i = 0; i < heights.size(); i++) {
            int height = heights[i];
            int width = 1;
            s = max(s, height * width);
            for (int j = i + 1; j < heights.size(); j++) {
                if (heights[j] < height) {
                    height = heights[j];
                }
                width += 1;
                s = max(s, height * width);
            }
        }
        return s;
    }
   };

   上述为的复杂度，导致时间超限。

2. 优化

   1. 单调栈

      https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/

   2. 
      

      代码

      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;
      }
      };