剑指 Offer II 039. 直方图最大矩形面积
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
注意：本题与主站 84 题相同： https://leetcode.cn/problems/largest-rectangle-in-histogram/
原站题解
golang 解法, 执行用时: 84 ms, 内存消耗: 9.7 MB, 提交时间: 2023-04-22 12:19:07
func largestRectangleArea(heights []int) int {
n := len(heights)
left, right := make([]int, n), make([]int, n)
for i := 0; i < n; i++ {
right[i] = n
}
mono_stack := []int{}
for i := 0; i < n; i++ {
for len(mono_stack) > 0 && heights[mono_stack[len(mono_stack)-1]] >= heights[i] {
right[mono_stack[len(mono_stack)-1]] = i
mono_stack = mono_stack[:len(mono_stack)-1]
}
if len(mono_stack) == 0 {
left[i] = -1
} else {
left[i] = mono_stack[len(mono_stack)-1]
}
mono_stack = append(mono_stack, i)
}
ans := 0
for i := 0; i < n; i++ {
ans = max(ans, (right[i] - left[i] - 1) * heights[i])
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
python3 解法, 执行用时: 200 ms, 内存消耗: 26.8 MB, 提交时间: 2023-04-22 12:18:55
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
left, right = [0] * n, [n] * n
mono_stack = list()
for i in range(n):
while mono_stack and heights[mono_stack[-1]] >= heights[i]:
right[mono_stack[-1]] = i
mono_stack.pop()
left[i] = mono_stack[-1] if mono_stack else -1
mono_stack.append(i)
ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0
return ans
java 解法, 执行用时: 18 ms, 内存消耗: 50.1 MB, 提交时间: 2023-04-22 12:18:32
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
Deque<Integer> mono_stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
right[mono_stack.peek()] = i;
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
}
cpp 解法, 执行用时: 100 ms, 内存消耗: 64.8 MB, 提交时间: 2023-04-22 12:18:22
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n, n);
stack<int> mono_stack;
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
right[mono_stack.top()] = i;
mono_stack.pop();
}
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};