Largest Rectangular Panel Under a Row of Fence Posts
Solve this Problemheights[i]. You want to nail up the widest possible rectangular banner that fits entirely under the tops of a contiguous run of posts — its height limited by the shortest post it spans. Given heights, return the largest possible banner area.
Checking every contiguous run of posts directly costs O(n²). The key insight for going faster: instead of asking "what's the shortest post in this run?" for every possible run, ask the reverse question for each post individually — "how far left and right can a rectangle at this exact height extend before hitting something shorter?" A monotonic stack of post indices, kept in strictly increasing height order, answers that in a single left-to-right pass: whenever a shorter post appears, every taller post still on the stack has just found its right boundary, and its left boundary is whatever remains below it on the stack — so its rectangle can be finalized and popped, once, forever. Appending one sentinel post of height 0 at the very end guarantees every remaining post gets flushed and finalized too.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ heights.length ≤ 12 - ◆
0 ≤ heights[i] ≤ 100 - ◆
The answer fits comfortably in a 32-bit signed integer for this input size
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Expand Around Every Starting Post
BruteFor every starting post i, extend a window rightward one post at a time, tracking the shortest post seen so far in the window (since a rectangle spanning several posts can only be as tall as its shortest member). At each extension, the candidate area is that running minimum height times the window's current width. Track the best area seen across every (start, end) pair. This checks all O(n²) windows directly, without any shortcut.
O(n²)O(1)1class Solution {
2 public int largestFencePanelArea(int[] heights) {
3 int n = heights.length;
4 int best = 0;
5 for (int i = 0; i < n; i++) {
6 int mn = heights[i];
7 for (int j = i; j < n; j++) {
8 mn = Math.min(mn, heights[j]);
9 best = Math.max(best, mn * (j - i + 1));
10 }
11 }
12 return best;
13 }
14}Optimal — Monotonic Stack of Increasing Post Heights
OptimalWalk left to right, keeping a stack of post indices whose heights are strictly increasing. When the current post is shorter than the post on top of the stack, that taller post can never extend any further right — pop it and finalize the largest rectangle that uses it as the limiting (shortest) height, with its width running from just after the new stack top back to the current index. Repeat until the stack's invariant holds again, then push the current post. A sentinel post of height 0 appended at the end forces every remaining post on the stack to be finalized. Every post is pushed and popped at most once, giving O(n) total work.
O(n)O(n)1class Solution {
2 public int largestFencePanelArea(int[] heights) {
3 int n = heights.length;
4 Deque<Integer> stack = new ArrayDeque<>();
5 int maxArea = 0;
6 for (int i = 0; i <= n; i++) {
7 int cur = (i == n) ? 0 : heights[i];
8 while (!stack.isEmpty() && heights[stack.peek()] >= cur) {
9 int top = stack.pop();
10 int height = heights[top];
11 int width = stack.isEmpty() ? i : i - stack.peek() - 1;
12 maxArea = Math.max(maxArea, height * width);
13 }
14 stack.push(i);
15 }
16 return maxArea;
17 }
18}