84 Largest Rectangle in Histogram 柱状图中最大的矩形
Description:
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.
Example:
histogram
Input: [2,1,5,6,2,3]
Output: 10
题目描述:
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 :
柱状图
输入: [2,1,5,6,2,3]
输出: 10
思路:
- 对每一个柱子, 寻找左边小于它的第一个柱子 left_index, 右边小于它的第一个柱子 right_index, result = max(height[i] * (right_index - left_index - 1)
时间复杂度O(n ^ 2), 空间复杂度O(1) - 单调栈
- 单调栈是一种特殊的栈, 栈中的元素依次递增(递减), 这就要求在入栈的时候, 如果该元素比栈顶元素大, 直接入栈, 否则弹出元素直到栈顶元素小于入栈元素
这样如果是需要入栈的元素比栈顶小, 说明它是栈顶的第一个右边小于它的元素, 其下标就是右边柱子 right_index, 左边的下标 left_index就是栈顶元素的下标, 单调栈里记录下标, 保证下标对应的 height值递增
时间复杂度O(n), 空间复杂度O(n)
代码:
C++:
class Solution
{
public:
int largestRectangleArea(vector<int>& heights)
{
heights.push_back(0);
stack<int> s;
int result = 0;
for (int i = 0; i < heights.size(); i++)
{
while (!s.empty() and heights[i] < heights[s.top()])
{
int cur = s.top();
s.pop();
result = max(result, heights[cur] * (s.empty() ? i : (i - s.top() - 1)));
}
s.push(i);
}
return result;
}
};
Java:
class Solution {
public int largestRectangleArea(int[] heights) {
int result = 0;
Stack<Integer> stack = new Stack<>();
int temp[] = new int[heights.length + 1];
for (int i = 0; i < heights.length; i++) temp[i] = heights[i];
for (int i = 0; i < temp.length; i++) {
while (!stack.empty() && temp[stack.peek()] > temp[i]) {
int cur = stack.pop();
result = Math.max(result, (stack.empty() ? i : (i - stack.peek() - 1)) * temp[cur]);
}
stack.push(i);
}
return result;
}
}
Python:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights += [0]
stack, result = [], 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
result = max(result, (i - stack[-2] - 1 if len(stack) > 1 else i) * heights[stack.pop()])
stack.append(i)
return result
