LeetCode 0084 - Largest Rectangle in Histogram
# Hints
- 单调栈
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given non-negative integers representing the histogram's bar height where the width of each bar is , find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is , 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
# 题意
给定 个连续摆放的矩形(形如柱形统计图),每个矩形的宽度为 ,高度为 ,求在这块图形内能圈出的最大连续矩形面积,不能越界。
# 题解
单调栈的经典问题。
详细题解待补,等将来写好单调栈的博客,再从此处引链接过去。
# AC代码
class Solution {
public:
int largestRectangleArea(vector<int> & heights) {
// 初始化
heights.push_back(-1);
int n = heights.size();
vector<int> lefts(n), rights(n);
// 主循环
stack<int> s;
for (int i = 0; i < n; i ++) {
// 出栈
while (!s.empty() && heights[s.top()] > heights[i]) {
rights[s.top()] = i - 1;
s.pop();
}
// 入栈
lefts[i] = (s.empty() ? 0 : s.top() + 1);
s.push(i);
}
// 求最大值
int res = 0;
for (int i = 0; i < n - 1; i ++) {
int area = (rights[i] - lefts[i] + 1) * heights[i];
res = max(res, area);
}
// 返回
heights.pop_back();
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01