Should I use Stack or ArrayDeque for the stack?

ArrayDeque. java.util.Stack extends Vector, so every push and pop takes a lock, and the JDK docs themselves point to Deque instead. Use push, pop and peek on the deque: they all work at the head, which is the top of the stack.

Why does the one-pass version use an int[] instead of a Deque?

A Deque boxes every index into an Integer object, and indices above 127 are new allocations. An int[] of size n + 1 plus a size counter holds the same stack with no objects at all, which matters when the method runs on large inputs many times.

Can heights[i] * width overflow an int?

Not within these constraints: at most 10⁶ times 2,000 is 2×10⁹, just under Integer.MAX_VALUE (2,147,483,647). With wider bounds, multiply in long ((long) heights[top] * (i - left - 1)) and return a long, because Java int arithmetic wraps silently.

Why does stack.peek() compare correctly with an int?

In heights[stack.peek()] the Integer is unboxed to an int index, so the array read is ordinary. The trap is comparing two boxed values with ==, which compares references; keep comparisons on unboxed int values or on the heights they index.

Is the brute force too slow in Java?

Not at 2,000 bars: about two million inner steps, which the JIT turns into a tight loop that finishes in a few milliseconds. It is the quadratic growth that hurts; at 10⁵ bars it would be 5×10⁹ steps.

Largest Rectangle in Histogram in Java: Brute Force and Monotonic Stack Solutions

largest_rectangle_area.java

Java 25.0

Not run yet

+ 8 hidden

Input

heights = [2, 4, 5, 3, 1, 3]

Expected

The bars 4, 5, 3 at indices 1 to 3 are all at least 3 tall, so a rectangle of height 3 and width 3 fits: 3 × 3 = 9. The tallest bar alone gives only 5.