题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例：

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

解答 & 代码

参考：★★☆☆单调栈结构(进阶）

1. 使用单调栈，求出每根柱子左、右两侧比它矮且离得最近的柱子下标

依次以每根柱子的高度作为高，左右两侧高度小于当前柱子的最近的两根柱子的下标之差 - 1 就是这个高度对应的宽度，就可以求出该高度对应的矩形面积，并更新最大面积

class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
   // 1. 使用单调栈，求出每根柱子左、右两侧比它矮且离得最近的柱子下标
   vector<vector<int>> nearstLow(heights.size(), vector<int>(2, 0));    // 存储每根柱子左、右离它最近的且高度比它低的柱子下标
   stack<vector<int>> s;    // 单调栈，存储柱子下标，从栈顶到栈底下标对应的柱子高度递减
   for(int i = 0; i < heights.size(); ++i)
   {
       while(!s.empty() && heights[i] < heights[s.top().back()])
       {
           vector<int> top = s.top();
           s.pop();
           for(auto it = top.begin(); it != top.end(); ++it)
           {
               nearstLow[*it][0] = s.empty() ? -1 : s.top().back();
               nearstLow[*it][1] = i;
           }
       }

       if(!s.empty() && heights[i] == heights[s.top().back()])
           s.top().push_back(i);
       else
           s.push(vector<int> (1, i));
   }
   while(!s.empty())
   {
       vector<int> top = s.top();
       s.pop();
       for(auto it = top.begin(); it != top.end(); ++it)
       {
           nearstLow[*it][0] = s.empty() ? -1 : s.top().back();
           nearstLow[*it][1] = heights.size();
       }
   }

   // 2. 依次以每根柱子的高度作为高，左右两侧最近的高度小于当前柱子的下标之差 - 1 就是这个高度对应的宽度
   // 求该高度对应的矩形面积，并更新最大面积
   int maxArea = 0;
   for(int i = 0; i < heights.size(); ++i)
   {
       int width = nearstLow[i][1] - nearstLow[i][0] - 1;
       int area = width * heights[i];
       maxArea = area > maxArea ? area : maxArea;
   }

   return maxArea;
}
};

执行结果： ``` 执行结果：通过

执行用时：432 ms, 在所有 C++ 提交中击败了 5.21% 的用户内存消耗：122.2 MB, 在所有 C++ 提交中击败了 5.00% 的用户 ```

CodeTop 企业题库

[困难] 84. 柱状图中最大的矩形

题目

解答 & 代码