来源：力扣（LeetCode）
链接: https://leetcode.cn/problems/largest-rectangle-in-histogram/
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
- 1 <= heights.length <= 1 0 5 10^5 105
- 0 <= heights[i] <= 1 0 4 10^4 104
- 暴力法：两层for循环，加找区间段最小的高度；
- 最小栈：本题理解就是最小栈，找每个柱子左右两边的离得最近的元素，可以使用栈的方式。元素依次入栈，如果入栈元素比栈顶元素大，则继续入栈，如果比栈顶元素小，说明栈顶元素的右边界找到了，左边界就是其下面的栈中元素，将该栈顶元素pop出栈，高度为它，宽度为（入栈的下标-此时栈顶元素-1）；一直这样while循环；
python实现
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
if n == 1:
return heights[0]
max_res = max(heights) # 最长的单柱子
for i in range(n-1):
for j in range(i+1, n):
max_res = max(max_res, min(heights[i:j+1]) * (j-i+1))
return max_res
c++实现
class Solution {
public:
int largestRectangleArea(vector& heights) {
int n = heights.size();
if (n==1)
return heights[0];
int max_res = 0;
for(int height: heights) {
if (height > max_res)
max_res = height;
}
for (int i=0; i
for (int j=i+1; j
int current_min_height = heights[i];
for (int k=i; k<=j; k++)
current_min_height = min(heights[k], current_min_height);
max_res = max(max_res, current_min_height*(j-i+1));
}
}
return max_res;
}
};
复杂度分析
- 时间复杂度： O ( n 3 ) O(n^3) O(n3) 中间找区间最小值也需要遍历一遍
- 空间复杂度： O ( 1 ) O(1) O(1)
python实现
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
if n == 1:
return heights[0]
max_res = max(heights) # add element
stack = []
heights = [0] + heights + [0] # 这里补0是为了开头元素以及末尾元素
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
tmp = stack.pop()
max_res = max(max_res, heights[tmp] * (i-stack[-1]-1))
stack.append(i)
return max_res
c++实现
class Solution {
public:
int largestRectangleArea(vector& heights) {
if (heights.size() == 1)
return heights[0];
vector stack;
heights.insert(heights.begin(), 0);
heights.insert(heights.end(), 0);
int max_area = 0;
for (int i=0; i
while (stack.size() != 0 && heights[i] < heights[stack.back()]) {
int tmp = stack.back();
stack.pop_back();
max_area = max(max_area, heights[tmp] * (i-stack.back()-1));
}
stack.push_back(i);
}
return max_area;
}
};
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
- https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
