84. 柱状图中最大的矩形
已解答
困难
相关标签
相关企业
给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入：heights = [2,4]输出：4提示：
1 <= heights.length <=1050 <= 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; } };
