84. Largest Rectangle in Histogram
給定一個整數數組 heights，表示直方圖中每個柱子的高度，其中每個柱子的寬度為 1，返回直方圖中最大的矩形面積。
範例 1：
輸入：heights = [2,1,5,6,2,3] 輸出：10 解釋：上圖所示為每個柱子寬度為 1 的直方圖。最大的矩形顯示在紅色區域，面積為 10 單位。
Python
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = []
max_area = 0
index = 0
while index < len(heights):
# If this bar is higher than the bar at the stack's top, push it
to the stack
if not stack or heights[index] >= heights[stack[-1]]:
stack.append(index)
index += 1
else:
# Pop the top
top_of_stack = stack.pop()
# Calculate the area with heights[top_of_stack] as the smallest
(or minimum height) bar 'h'
area = (heights[top_of_stack] *
((index - stack[-1] - 1) if stack else index))
# Update max_area, if needed
max_area = max(max_area, area)
# Now pop the remaining bars from stack and calculate area with each
popped bar
while stack:
top_of_stack = stack.pop()
area = (heights[top_of_stack] *
((index - stack[-1] - 1) if stack else index))
max_area = max(max_area, area)
return max_area
30.48MB, 673ms
C++
#include <vector>
#include <stack>
#include <algorithm>
class Solution {
public:
int largestRectangleArea(std::vector<int>& heights) {
std::stack<int> stack;
int max_area = 0;
int index = 0;
while (index < heights.size()) {
// If this bar is higher than the bar at the stack's top,
push it to the stack
if (stack.empty() || heights[index] >= heights[stack.top()]) {
stack.push(index++);
} else {
// Pop the top
int top_of_stack = stack.top();
stack.pop();
// Calculate the area with heights[top_of_stack] as the smallest
(or minimum height) bar 'h'
int area = heights[top_of_stack] * (stack.empty() ? index :
index - stack.top() - 1);
// Update max_area, if needed
max_area = std::max(max_area, area);
}
}
// Now pop the remaining bars from stack and calculate area with each
popped bar
while (!stack.empty()) {
int top_of_stack = stack.top();
stack.pop();
int area = heights[top_of_stack] * (stack.empty() ? index :
index - stack.top() - 1);
max_area = std::max(max_area, area);
}
return max_area;
}
};
79.46MB, 108ms
Javascript
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
let stack = [];
let maxArea = 0;
let index = 0;
while (index < heights.length) {
// If this bar is higher than the bar at the stack's top, push it to the stack
if (stack.length === 0 || heights[index] >= heights[stack[stack.length - 1]]) {
stack.push(index++);
} else {
// Pop the top
let topOfStack = stack.pop();
// Calculate the area with heights[topOfStack] as the smallest (or minimum height) bar 'h'
let area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
// Update maxArea, if needed
maxArea = Math.max(maxArea, area);
}
}
// Now pop the remaining bars from stack and calculate area with each popped bar
while (stack.length > 0) {
let topOfStack = stack.pop();
let area = heights[topOfStack] * (stack.length === 0 ? index : index - stack[stack.length - 1] - 1);
maxArea = Math.max(maxArea, area);
}
return maxArea;
};
62.26MB, 86ms
