LeetCode-84. Largest Rectangle in Histogram

LeetCode-84. 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.

Example:

Input: [2,1,5,6,2,3]Output: 10

题解：暴力枚举超时了，参考答案使用单调栈维护。

​

class Solution {public: int largestRectangleArea(vector& heights) { heights.push_back(0); int res = 0, n = heights.size(), i = 0; stack s; while(i < n) { if (s.empty() == true || heights[i] > heights[s.top()]) { s.push(i++); } else { int t = s.top(); s.pop(); if (s.empty() == false) { res = max(res, heights[t] * (i - s.top() - 1)); } else { res = max(res, heights[t] * i); } } } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。