84. 柱状图中最大的矩形

84. 柱状图中最大的矩形

已解答

困难

相关标签

相关企业

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入：heights = [2,4]输出：4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

学习官方题解，left和right内的为宽

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