LeetCode|84.直方图中最大矩阵 LeetCode|C++

Largest Rectangle in Histogram 问题描述： Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

文章图片

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
参考答案：

class Solution { public: int largestRectangleArea(vector& heights) { stack s; int i = 0; int maxarea = 0; while (i < heights.size()) { if (s.empty() || heights[i] >= heights[s.top()]) s.push(i++); else { int h = heights[s.top()]; s.pop(); int w = s.empty() ? i : i-s.top()-1; maxarea = max(maxarea, h*w); } }while (!s.empty()) { int h = heights[s.top()]; s.pop(); int w = s.empty() ? i : i-s.top()-1; maxarea = max(maxarea, h*w); }return maxarea; } };

性能： 【LeetCode|84.直方图中最大矩阵】