Problem
Given an array of bar heights, find the area of the largest rectangle in the histogram.
Example
Input: [2,1,5,6,2,3]
Output: 10
The 5 and 6 form a rectangle of width 2, height 5.Solution
Monotonic stack. For each bar, find how far left and right it can extend without finding a shorter bar.
def largest_rectangle_area(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] > h:
top = stack.pop()
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * width)
stack.append(i)
return max_areafunction largestRectangleArea(heights) {
const stack = [];
let maxArea = 0;
heights.push(0);
for (let i = 0; i < heights.length; i++) {
while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
const top = stack.pop();
const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, heights[top] * width);
}
stack.push(i);
}
return maxArea;
}int largestRectangleArea(vector<int>& heights) {
stack<int> st;
int maxArea = 0;
heights.push_back(0);
for (int i = 0; i < heights.size(); i++) {
while (!st.empty() && heights[st.top()] > heights[i]) {
int top = st.top(); st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = max(maxArea, heights[top] * width);
}
st.push(i);
}
return maxArea;
}public int largestRectangleArea(int[] heights) {
Stack<Integer> st = new Stack<>();
int maxArea = 0;
int[] h = Arrays.copyOf(heights, heights.length + 1);
for (int i = 0; i < h.length; i++) {
while (!st.isEmpty() && h[st.peek()] > h[i]) {
int top = st.pop();
int width = st.isEmpty() ? i : i - st.peek() - 1;
maxArea = Math.max(maxArea, h[top] * width);
}
st.push(i);
}
return maxArea;
}Complexity
- Time: O(n)
- Space: O(n)
Explanation
Stack maintains increasing heights. When we hit a shorter bar, we pop and compute rectangles. The sentinel 0 forces the stack to drain.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?