84. Largest Rectangle in Histogram
/*
* @lc app=leetcode id=84 lang=cpp
*
* [84] Largest Rectangle in Histogram
*
* https://leetcode.com/problems/largest-rectangle-in-histogram/description/
*
* algorithms
* Hard (45.83%)
* Likes: 18224
* Dislikes: 326
* Total Accepted: 1.2M
* Total Submissions: 2.5M
* Testcase Example: '[2,1,5,6,2,3]'
*
* Given an array of integers heights representing the histogram's bar height
* where the width of each bar is 1, return the area of the largest rectangle
* in the histogram.
*
*
* Example 1:
*
*
* Input: heights = [2,1,5,6,2,3]
* Output: 10
* Explanation: The above is a histogram where width of each bar is 1.
* The largest rectangle is shown in the red area, which has an area = 10
* units.
*
*
* Example 2:
*
*
* Input: heights = [2,4]
* Output: 4
*
*
*
* Constraints:
*
*
* 1 <= heights.length <= 10^5
* 0 <= heights[i] <= 10^4
*
*
*/
// @lc code=start
class Solution {
public:
int largestRectangleArea(vector<int>& heights)
{
heights.push_back(0);
stack<int> stk;
int i = 0;
int n = heights.size();
int maxArea = 0;
for (int i = 0; i < n; ++i)
{
while (!stk.empty() && heights[stk.top()] > heights[i])
{
int h = heights[stk.top()]; stk.pop();
int w = stk.empty() ? i : i - stk.top() - 1;
maxArea = max(maxArea, h * w);
}
stk.push(i);
}
return maxArea;
}
};
// @lc code=end
- T:
- S: