0%

[Leetcode]Largest Rectangle in Histogram(C++)

题目描述

题目链接:Largest Rectangle in Histogram

例子

例子 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.

例子 2

Input: heights = [2,4]
Output: 4

Constraints

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^4

解题思路

可以用一个栈来维护之前遇到的最大高度,来作为是否更新结果的判断标准,遍历所有高度:

  • 栈为空时,直接将当前高度的下标压入栈中,检查下一位置
  • 栈顶元素小于当前高度时,结果不会变(因为还是只能取栈顶元素高度构建长方形),同样压入栈中,检查下一位置
  • 栈顶元素大于当前高度时,意味着之后的 bar 不能利用栈顶高度构建长方形,因此最大结果 有可能更新,因此需要进行更新,方法如下:
    • 栈顶取出之前最大高度的下标作为高度
    • 用当前下标到下一个栈顶的位置的距离作为宽度(需要减一,因为下一个栈顶的高度有可能比当前高度低,不一定能用)
    • 宽 * 高作为当前面积来进行最优值更新
    • 重复该操作,直至遇到栈为空或栈顶小于当前高度

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stack>
#include <vector>

class Solution {
public:
int largestRectangleArea(std::vector<int>& heights) {
// place holder
heights.push_back(0);
std::stack<int> stk;
int result = 0;
int idx = 0;
while (idx < heights.size()) {
// #1 stack empty, push the height to the stack
// #2 current height higher than the previous highest height
if (stk.empty() || heights[idx] >= heights[stk.top()]) {
stk.push(idx++);
} else {
// #3 meet a lower bar, the previous highest bar is unuseable,
// hence remove it from stack, update the result (compare to use
// current height to the top of stack), keep doing this step,
// until meet another lower bar
int h = heights[stk.top()];
stk.pop();
int w = stk.empty() ? idx : idx - stk.top() - 1;
result = std::max(result, h * w);
}
}

return result;
}
};
  • 时间复杂度: O(n) — 每个元素最多只被遍历两次(压入一次,往回检查一次)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 84.LargestRectangleInHistogram.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions