Largest Rectangle in Histogram
Problem
Given an array of non-negative bar heights of equal width, return the area of the largest rectangle that fits within the histogram.
Input
heights = [2, 1, 5, 6, 2, 3]Output
10A monotonic-increasing stack of indices lets us pop on each shorter bar to find that bar's max-area rectangle.
def largest_rectangle(heights):
stack = []
best = 0
for i in range(len(heights) + 1):
h = 0 if i == len(heights) else heights[i]
while stack and heights[stack[-1]] > h:
top = stack.pop()
left = stack[-1] if stack else -1
width = i - left - 1
best = max(best, heights[top] * width)
stack.append(i)
return bestfunction largestRectangle(heights) {
const stack = [];
let best = 0;
for (let i = 0; i <= heights.length; i++) {
const h = i === heights.length ? 0 : heights[i];
while (stack.length && heights[stack[stack.length - 1]] > h) {
const top = stack.pop();
const left = stack.length ? stack[stack.length - 1] : -1;
const width = i - left - 1;
best = Math.max(best, heights[top] * width);
}
stack.push(i);
}
return best;
}class Solution {
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int best = 0;
for (int i = 0; i <= heights.length; i++) {
int h = i == heights.length ? 0 : heights[i];
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int top = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
best = Math.max(best, heights[top] * (i - left - 1));
}
stack.push(i);
}
return best;
}
}int largestRectangleArea(vector<int>& heights) {
stack<int> st;
int best = 0, n = heights.size();
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!st.empty() && heights[st.top()] > h) {
int top = st.top(); st.pop();
int left = st.empty() ? -1 : st.top();
best = max(best, heights[top] * (i - left - 1));
}
st.push(i);
}
return best;
}