Monotonic Stack

Keep a stack in sorted order so every element finds its next greater or smaller neighbor in one O(n) pass.

IntermediateRead first: Stacks & Queues

How It Works

Some problems ask the same question about every element: what's the next value to its right that's bigger? (Or smaller, or the nearest one on the left.) Scanning outward from each element answers it in O(n²). A monotonic stack answers all of them in one left-to-right pass.

The stack holds the elements that are still waiting for an answer, and it stays sorted. For next greater, the waiting values never increase from bottom to top. When a new value arrives, it's the answer for every waiting value smaller than it, and those are exactly the ones on top. Pop them, record the answer, then push the new value, which now waits too. It's the first greater value for each one it pops, because anything greater that came earlier would already have popped them.

nums = [4, 5, 2, 10, 8]

 i  value  popped -> answer   stack after
 0      4  none               [4]
 1      5  4 -> 5             [5]
 2      2  none               [5, 2]
 3     10  2 -> 10, 5 -> 10   [10]
 4      8  none               [10, 8]

10 and 8 are never popped, so they keep -1.
result = [5, 10, 10, -1, -1]

The stack is shown as values to keep it readable. The code stores indices, so it knows where to write each answer.

Next Greater Element, Step by Step

Step 1 of 10

nums

stack (values)

result

Current value and what it just did
Waiting on the stack
Answered

Every answer starts as -1. Scan left to right, keeping the values that are still waiting for something greater on the stack.

Nothing is waiting, so push 4. It waits for its own answer.

5 beats 4 on top, so it's the first greater value after it. Pop it and set result[0] = 5.

The stack is empty now, so push 5. It waits for its own answer.

2 isn't bigger than 5 on top, so nothing pops. Push it. The stack reads 5, 2, which never increases from bottom to top.

10 beats 2 on top, so it's the first greater value after it. Pop it and set result[2] = 10. The new top is smaller too, so keep popping.

10 beats 5 on top, so it's the first greater value after it. Pop it and set result[1] = 10.

The stack is empty now, so push 10. It waits for its own answer.

8 isn't bigger than 10 on top, so nothing pops. Push it. The stack reads 10, 8, which never increases from bottom to top.

The scan is done. 10 and 8 never met anything greater, so they keep -1. result = [5, 10, 10, -1, -1], and each index was pushed once and popped at most once.

All 10 steps as text

Every answer starts as -1. Scan left to right, keeping the values that are still waiting for something greater on the stack.
Nothing is waiting, so push 4. It waits for its own answer.
5 beats 4 on top, so it's the first greater value after it. Pop it and set result[0] = 5.
The stack is empty now, so push 5. It waits for its own answer.
2 isn't bigger than 5 on top, so nothing pops. Push it. The stack reads 5, 2, which never increases from bottom to top.
10 beats 2 on top, so it's the first greater value after it. Pop it and set result[2] = 10. The new top is smaller too, so keep popping.
10 beats 5 on top, so it's the first greater value after it. Pop it and set result[1] = 10.
The stack is empty now, so push 10. It waits for its own answer.
8 isn't bigger than 10 on top, so nothing pops. Push it. The stack reads 10, 8, which never increases from bottom to top.
The scan is done. 10 and 8 never met anything greater, so they keep -1. result = [5, 10, 10, -1, -1], and each index was pushed once and popped at most once.

There's a loop inside a loop, but the scan is still O(n). Each element is pushed exactly once and popped at most once. One step can pop many elements, but only ones that earlier steps pushed, so across the whole scan the inner loop runs at most n times in total. That's O(n) amortized time, plus O(n) space for the stack in the worst case (a decreasing input never pops anything).

Next greater. Pop while the top is smaller than the current value. The stack decreases from bottom to top.
Next smaller. Flip the comparison and pop while the top is larger. The stack increases from bottom to top.
Previous greater. Pop while the top is less than or equal to the current value. Whatever is left on top is the nearest earlier value that's bigger, so read it before you push. Flip the comparison for previous smaller.
Circular arrays. Loop i from 0 to 2n - 1 and use i % n, so values near the end can find their answer near the start.

When to Reach for It

For each element, you need the next or previous element that is greater or smaller.
The question asks how long until something bigger arrives: a warmer day, a higher price, a taller building.
You need how far each bar extends left or right before something shorter blocks it, as in histograms and stock spans.
You keep a subsequence in order while greedily dropping earlier elements that a later one beats, as in Remove K Digits.
The brute force scans outward from every index, and n is large enough that O(n²) won't pass.

Complexity

Operation	Time	Space
Next or previous greater/smaller for every element	O(n)	O(n)
Circular array (scan twice)	O(n)	O(n)
Largest rectangle in a histogram	O(n)	O(n)
Brute force: scan outward from each element	O(n²)	O(1) beyond the output

The Template

Next Greater Element

Walk left to right with a stack of indices whose values haven't met anything greater yet. When nums[i] arrives, pop every waiting index with a smaller value and record nums[i] as its answer, then push i. Indices still on the stack at the end never met a greater value, so they keep -1.

The stack stores indices rather than values. An index tells you where to write the answer, and the value is one lookup away. Problems that want a distance, like Daily Temperatures below, need the index anyway.

The comparison is strict (<), so an equal value doesn't count as greater: in [5, 5, 4] the first 5 stays on the stack when the second one arrives. Use <= if the problem counts equal values as an answer.

Time O(n)Space O(n)

def next_greater(nums: list[int]) -> list[int]:
    """For each value in `nums`, the next value to its right that is strictly
    greater, or -1 if there isn't one."""
    result = [-1] * len(nums)
    # Indices still waiting for a greater value. Their values never increase
    # from bottom to top, so the smallest waiting value is always on top.
    stack: list[int] = []
    for i in range(len(nums)):
        # nums[i] answers every waiting value smaller than it, and those are all on top.
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)  # Now nums[i] waits for its own answer.
    return result  # Whatever is still on the stack keeps -1.


if __name__ == "__main__":
    print(next_greater([4, 5, 2, 10, 8]))  # [5, 10, 10, -1, -1]
    print(next_greater([2, 7, 3, 5, 4, 6, 8]))  # [7, 8, 5, 6, 6, 8, -1]
    print(next_greater([5, 5, 4]))  # [-1, -1, -1]

// For each value in `nums`, the next value to its right that is strictly
// greater, or -1 if there isn't one.
export function nextGreater(nums: number[]): number[] {
  const result = new Array<number>(nums.length).fill(-1);
  // Indices still waiting for a greater value. Their values never increase
  // from bottom to top, so the smallest waiting value is always on top.
  const stack: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    // nums[i] answers every waiting value smaller than it, and those are all on top.
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i); // Now nums[i] waits for its own answer.
  }
  return result; // Whatever is still on the stack keeps -1.
}

console.log(JSON.stringify(nextGreater([4, 5, 2, 10, 8]))); // [5,10,10,-1,-1]
console.log(JSON.stringify(nextGreater([2, 7, 3, 5, 4, 6, 8]))); // [7,8,5,6,6,8,-1]
console.log(JSON.stringify(nextGreater([5, 5, 4]))); // [-1,-1,-1]

package main

import "fmt"

// nextGreater returns, for each value in nums, the next value to its right
// that is strictly greater, or -1 if there isn't one.
func nextGreater(nums []int) []int {
	result := make([]int, len(nums))
	for i := range result {
		result[i] = -1
	}
	// Indices still waiting for a greater value. Their values never increase
	// from bottom to top, so the smallest waiting value is always on top.
	stack := []int{}
	for i := range nums {
		// nums[i] answers every waiting value smaller than it, and those are all on top.
		for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
			result[stack[len(stack)-1]] = nums[i]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i) // Now nums[i] waits for its own answer.
	}
	return result // Whatever is still on the stack keeps -1.
}

func main() {
	fmt.Println(nextGreater([]int{4, 5, 2, 10, 8}))      // [5 10 10 -1 -1]
	fmt.Println(nextGreater([]int{2, 7, 3, 5, 4, 6, 8})) // [7 8 5 6 6 8 -1]
	fmt.Println(nextGreater([]int{5, 5, 4}))             // [-1 -1 -1]
}

using System;
using System.Collections.Generic;

public class Solution
{
    // For each value in nums, the next value to its right that is strictly
    // greater, or -1 if there isn't one.
    public static int[] NextGreater(int[] nums)
    {
        var result = new int[nums.Length];
        Array.Fill(result, -1);
        // Indices still waiting for a greater value. Their values never increase
        // from bottom to top, so the smallest waiting value is always on top.
        var stack = new Stack<int>();
        for (int i = 0; i < nums.Length; i++)
        {
            // nums[i] answers every waiting value smaller than it, and those are all on top.
            while (stack.Count > 0 && nums[stack.Peek()] < nums[i])
            {
                result[stack.Pop()] = nums[i];
            }
            stack.Push(i); // Now nums[i] waits for its own answer.
        }
        return result; // Whatever is still on the stack keeps -1.
    }

    public static void Main()
    {
        Console.WriteLine(Format(NextGreater(new[] { 4, 5, 2, 10, 8 }))); // [5, 10, 10, -1, -1]
        Console.WriteLine(Format(NextGreater(new[] { 2, 7, 3, 5, 4, 6, 8 }))); // [7, 8, 5, 6, 6, 8, -1]
        Console.WriteLine(Format(NextGreater(new[] { 5, 5, 4 }))); // [-1, -1, -1]
    }

    static string Format(int[] values) => "[" + string.Join(", ", values) + "]";
}

import java.util.ArrayDeque;
import java.util.Arrays;

public class Solution {
    // For each value in nums, the next value to its right that is strictly
    // greater, or -1 if there isn't one.
    static int[] nextGreater(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        // Indices still waiting for a greater value. Their values never increase
        // from bottom to top, so the smallest waiting value is always on top.
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // nums[i] answers every waiting value smaller than it, and those are all on top.
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i];
            }
            stack.push(i); // Now nums[i] waits for its own answer.
        }
        return result; // Whatever is still on the stack keeps -1.
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[] {4, 5, 2, 10, 8}))); // [5, 10, 10, -1, -1]
        System.out.println(Arrays.toString(nextGreater(new int[] {2, 7, 3, 5, 4, 6, 8}))); // [7, 8, 5, 6, 6, 8, -1]
        System.out.println(Arrays.toString(nextGreater(new int[] {5, 5, 4}))); // [-1, -1, -1]
    }
}

Worked Problems

Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.

Daily Temperatures

MEDIUMLeetCode 739

Problem

You're given a list of daily temperatures. For each day, return how many days you'd have to wait for a strictly warmer one. If no warmer day ever comes, return 0 for that day.

Example: [73, 74, 75, 71, 69, 72, 76, 73] returns [1, 1, 4, 2, 1, 1, 0, 0]. After the 75 on day 2, the next warmer day is the 76 on day 6, four days later.

Show Solution

Approach

This is the next greater template with a different answer: instead of the warmer temperature, you record how far away it is. That's why the stack must hold indices. When today pops an earlier day, the wait is i - day.

Days that never get popped keep 0, which is exactly what the problem wants for a day with no warmer future. Equal temperatures aren't warmer, so the comparison stays strict: in [60, 50, 50, 70], both 50s wait for the 70. Each day is pushed once and popped at most once, so the scan is O(n).

Time O(n)Space O(n)

def daily_temperatures(temperatures: list[int]) -> list[int]:
    """For each day, how many days you wait for a strictly warmer one, or 0 if
    none comes."""
    answer = [0] * len(temperatures)
    # Days still waiting for a warmer day, coldest on top. The answer is a
    # distance, so the stack holds indices rather than temperatures.
    stack: list[int] = []
    for i in range(len(temperatures)):
        # Today is the first warmer day for every colder day on top of the stack.
        while stack and temperatures[stack[-1]] < temperatures[i]:
            day = stack.pop()
            answer[day] = i - day
        stack.append(i)
    return answer  # Days left on the stack never warm up, so they keep 0.


if __name__ == "__main__":
    print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))  # [1, 1, 4, 2, 1, 1, 0, 0]
    print(daily_temperatures([30, 40, 50, 60]))  # [1, 1, 1, 0]
    print(daily_temperatures([60, 50, 50, 70]))  # [3, 2, 1, 0]

// For each day, how many days you wait for a strictly warmer one, or 0 if
// none comes.
export function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array<number>(temperatures.length).fill(0);
  // Days still waiting for a warmer day, coldest on top. The answer is a
  // distance, so the stack holds indices rather than temperatures.
  const stack: number[] = [];
  for (let i = 0; i < temperatures.length; i++) {
    // Today is the first warmer day for every colder day on top of the stack.
    while (stack.length > 0 && temperatures[stack[stack.length - 1]] < temperatures[i]) {
      const day = stack.pop()!;
      answer[day] = i - day;
    }
    stack.push(i);
  }
  return answer; // Days left on the stack never warm up, so they keep 0.
}

console.log(JSON.stringify(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))); // [1,1,4,2,1,1,0,0]
console.log(JSON.stringify(dailyTemperatures([30, 40, 50, 60]))); // [1,1,1,0]
console.log(JSON.stringify(dailyTemperatures([60, 50, 50, 70]))); // [3,2,1,0]

package main

import "fmt"

// dailyTemperatures returns, for each day, how many days you wait for a
// strictly warmer one, or 0 if none comes.
func dailyTemperatures(temperatures []int) []int {
	answer := make([]int, len(temperatures))
	// Days still waiting for a warmer day, coldest on top. The answer is a
	// distance, so the stack holds indices rather than temperatures.
	stack := []int{}
	for i := range temperatures {
		// Today is the first warmer day for every colder day on top of the stack.
		for len(stack) > 0 && temperatures[stack[len(stack)-1]] < temperatures[i] {
			day := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			answer[day] = i - day
		}
		stack = append(stack, i)
	}
	return answer // Days left on the stack never warm up, so they keep 0.
}

func main() {
	fmt.Println(dailyTemperatures([]int{73, 74, 75, 71, 69, 72, 76, 73})) // [1 1 4 2 1 1 0 0]
	fmt.Println(dailyTemperatures([]int{30, 40, 50, 60}))                 // [1 1 1 0]
	fmt.Println(dailyTemperatures([]int{60, 50, 50, 70}))                 // [3 2 1 0]
}

using System;
using System.Collections.Generic;

public class Solution
{
    // For each day, how many days you wait for a strictly warmer one, or 0 if
    // none comes.
    public static int[] DailyTemperatures(int[] temperatures)
    {
        var answer = new int[temperatures.Length];
        // Days still waiting for a warmer day, coldest on top. The answer is a
        // distance, so the stack holds indices rather than temperatures.
        var stack = new Stack<int>();
        for (int i = 0; i < temperatures.Length; i++)
        {
            // Today is the first warmer day for every colder day on top of the stack.
            while (stack.Count > 0 && temperatures[stack.Peek()] < temperatures[i])
            {
                int day = stack.Pop();
                answer[day] = i - day;
            }
            stack.Push(i);
        }
        return answer; // Days left on the stack never warm up, so they keep 0.
    }

    public static void Main()
    {
        Console.WriteLine(Format(DailyTemperatures(new[] { 73, 74, 75, 71, 69, 72, 76, 73 }))); // [1, 1, 4, 2, 1, 1, 0, 0]
        Console.WriteLine(Format(DailyTemperatures(new[] { 30, 40, 50, 60 }))); // [1, 1, 1, 0]
        Console.WriteLine(Format(DailyTemperatures(new[] { 60, 50, 50, 70 }))); // [3, 2, 1, 0]
    }

    static string Format(int[] values) => "[" + string.Join(", ", values) + "]";
}

import java.util.ArrayDeque;
import java.util.Arrays;

public class Solution {
    // For each day, how many days you wait for a strictly warmer one, or 0 if
    // none comes.
    static int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        // Days still waiting for a warmer day, coldest on top. The answer is a
        // distance, so the stack holds indices rather than temperatures.
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < temperatures.length; i++) {
            // Today is the first warmer day for every colder day on top of the stack.
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int day = stack.pop();
                answer[day] = i - day;
            }
            stack.push(i);
        }
        return answer; // Days left on the stack never warm up, so they keep 0.
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(dailyTemperatures(new int[] {73, 74, 75, 71, 69, 72, 76, 73}))); // [1, 1, 4, 2, 1, 1, 0, 0]
        System.out.println(Arrays.toString(dailyTemperatures(new int[] {30, 40, 50, 60}))); // [1, 1, 1, 0]
        System.out.println(Arrays.toString(dailyTemperatures(new int[] {60, 50, 50, 70}))); // [3, 2, 1, 0]
    }
}

Largest Rectangle in Histogram

HARDLeetCode 84

Problem

You're given the heights of the bars in a histogram, where every bar is 1 unit wide. Return the area of the largest rectangle that fits entirely inside the bars.

Example: [2, 1, 5, 6, 2, 3] returns 10. The bars of height 5 and 6 stand side by side, so a rectangle 5 high and 2 wide fits across them.

Show Solution

Approach

A rectangle is only as tall as the shortest bar it covers. So turn the question around: for each bar, how wide can a rectangle of exactly that bar's height get? It stretches left and right until it hits a shorter bar on each side. Those are the previous smaller and next smaller elements, and one stack finds both.

          .
       #  #
       #  #
       #  #     .
 .     #  #  .  .
 .  .  #  #  .  .
 2  1  5  6  2  3

The bars of height 5 and 6 share a rectangle 5 high and 2 wide (marked #). Its area, 10, is the answer.

Keep bar indices on the stack with heights increasing from bottom to top. When bar i is shorter than the bar on top, that bar's rectangle can't reach i, so pop it and measure. Its right edge is i - 1. Its left edge is just past the bar now on top of the stack, the nearest shorter bar on its left, or -1 if the stack is empty. So the width is i - left - 1.

A height of 0 after the last bar is shorter than everything, so it pops every bar that's left. No separate cleanup loop is needed.
The pop uses >=, so a bar of equal height gets popped too, and its measured width stops short at i - 1. That's harmless: the later bar inherits the same shorter neighbor on the left and measures the full width when its turn comes.

Measuring Each Bar's Rectangle

Step 1 of 14

heights

stack (indices)

Bar being pushed or measured
On the stack, rectangle still open
Measured, and the best rectangle

Scan the bars with a stack of indices whose heights increase from bottom to top. A bar's rectangle stays open, still growing right, while it's on the stack.

The stack is empty, so push bar 0 (height 2). No bar on its left is shorter, so its rectangle can reach the left edge.

Bar 1 (height 1) is shorter than bar 0 (height 2), so pop 0. Its width is 1 - (-1) - 1 = 1 because nothing shorter is left of it. Area 2, the new best.

The stack is empty, so push bar 1 (height 1). No bar on its left is shorter, so its rectangle can reach the left edge.

Bar 2 (height 5) is taller than bar 1 (height 1) on top, so nothing closes. Push 2: its rectangle is open.

Bar 3 (height 6) is taller than bar 2 (height 5) on top, so nothing closes. Push 3: its rectangle is open.

Bar 4 (height 2) is shorter than bar 3 (height 6), so pop 3. Its width is 4 - 2 - 1 = 1 because bar 2 is the nearest shorter bar on its left. Area 6, the new best.

Bar 4 (height 2) is shorter than bar 2 (height 5), so pop 2. Its width is 4 - 1 - 1 = 2 because bar 1 is the nearest shorter bar on its left. Area 10, the new best.

Bar 4 (height 2) is taller than bar 1 (height 1) on top, so the popping stops. Push 4: its rectangle is open.

Bar 5 (height 3) is taller than bar 4 (height 2) on top, so nothing closes. Push 5: its rectangle is open.

The sentinel 0 is shorter than bar 5 (height 3), so pop 5. Its width is 6 - 4 - 1 = 1 because bar 4 is the nearest shorter bar on its left. Area 3, which doesn't beat 10.

The sentinel 0 is shorter than bar 4 (height 2), so pop 4. Its width is 6 - 1 - 1 = 4 because bar 1 is the nearest shorter bar on its left. Area 8, which doesn't beat 10.

The sentinel 0 is shorter than bar 1 (height 1), so pop 1. Its width is 6 - (-1) - 1 = 6 because nothing shorter is left of it. Area 6, which doesn't beat 10.

The sentinel emptied the stack, so every bar has been measured. Return best = 10, the 5 x 2 rectangle across bars 2 to 3.

All 14 steps as text

Scan the bars with a stack of indices whose heights increase from bottom to top. A bar's rectangle stays open, still growing right, while it's on the stack.
The stack is empty, so push bar 0 (height 2). No bar on its left is shorter, so its rectangle can reach the left edge.
Bar 1 (height 1) is shorter than bar 0 (height 2), so pop 0. Its width is 1 - (-1) - 1 = 1 because nothing shorter is left of it. Area 2, the new best.
The stack is empty, so push bar 1 (height 1). No bar on its left is shorter, so its rectangle can reach the left edge.
Bar 2 (height 5) is taller than bar 1 (height 1) on top, so nothing closes. Push 2: its rectangle is open.
Bar 3 (height 6) is taller than bar 2 (height 5) on top, so nothing closes. Push 3: its rectangle is open.
Bar 4 (height 2) is shorter than bar 3 (height 6), so pop 3. Its width is 4 - 2 - 1 = 1 because bar 2 is the nearest shorter bar on its left. Area 6, the new best.
Bar 4 (height 2) is shorter than bar 2 (height 5), so pop 2. Its width is 4 - 1 - 1 = 2 because bar 1 is the nearest shorter bar on its left. Area 10, the new best.
Bar 4 (height 2) is taller than bar 1 (height 1) on top, so the popping stops. Push 4: its rectangle is open.
Bar 5 (height 3) is taller than bar 4 (height 2) on top, so nothing closes. Push 5: its rectangle is open.
The sentinel 0 is shorter than bar 5 (height 3), so pop 5. Its width is 6 - 4 - 1 = 1 because bar 4 is the nearest shorter bar on its left. Area 3, which doesn't beat 10.
The sentinel 0 is shorter than bar 4 (height 2), so pop 4. Its width is 6 - 1 - 1 = 4 because bar 1 is the nearest shorter bar on its left. Area 8, which doesn't beat 10.
The sentinel 0 is shorter than bar 1 (height 1), so pop 1. Its width is 6 - (-1) - 1 = 6 because nothing shorter is left of it. Area 6, which doesn't beat 10.
The sentinel emptied the stack, so every bar has been measured. Return best = 10, the 5 x 2 rectangle across bars 2 to 3.

Time O(n)Space O(n)

def largest_rectangle_area(heights: list[int]) -> int:
    """Area of the largest rectangle that fits inside the histogram `heights`,
    where every bar is 1 wide."""
    best = 0
    # Bars whose rectangles are still growing to the right. Heights strictly
    # increase from bottom to top, so the bar under each one is the nearest
    # shorter bar on its left.
    stack: list[int] = []
    for i in range(len(heights) + 1):
        # A height of 0 after the last bar closes every rectangle still open.
        height = 0 if i == len(heights) else heights[i]
        while stack and heights[stack[-1]] >= height:
            # Measure the rectangle of the top bar's height that ends just before i.
            top = stack.pop()
            left = stack[-1] if stack else -1
            best = max(best, heights[top] * (i - left - 1))
        stack.append(i)
    return best


if __name__ == "__main__":
    print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))  # 10
    print(largest_rectangle_area([2, 4]))  # 4
    print(largest_rectangle_area([6, 2, 5, 4, 5, 1, 6]))  # 12
    print(largest_rectangle_area([3, 3, 3]))  # 9

// Area of the largest rectangle that fits inside the histogram `heights`,
// where every bar is 1 wide.
export function largestRectangleArea(heights: number[]): number {
  let best = 0;
  // Bars whose rectangles are still growing to the right. Heights strictly
  // increase from bottom to top, so the bar under each one is the nearest
  // shorter bar on its left.
  const stack: number[] = [];
  for (let i = 0; i <= heights.length; i++) {
    // A height of 0 after the last bar closes every rectangle still open.
    const height = i === heights.length ? 0 : heights[i];
    while (stack.length > 0 && heights[stack[stack.length - 1]] >= height) {
      // Measure the rectangle of the top bar's height that ends just before i.
      const top = stack.pop()!;
      const left = stack.length > 0 ? stack[stack.length - 1] : -1;
      best = Math.max(best, heights[top] * (i - left - 1));
    }
    stack.push(i);
  }
  return best;
}

console.log(largestRectangleArea([2, 1, 5, 6, 2, 3])); // 10
console.log(largestRectangleArea([2, 4])); // 4
console.log(largestRectangleArea([6, 2, 5, 4, 5, 1, 6])); // 12
console.log(largestRectangleArea([3, 3, 3])); // 9

package main

import "fmt"

// largestRectangleArea returns the area of the largest rectangle that fits
// inside the histogram heights, where every bar is 1 wide.
func largestRectangleArea(heights []int) int {
	best := 0
	// Bars whose rectangles are still growing to the right. Heights strictly
	// increase from bottom to top, so the bar under each one is the nearest
	// shorter bar on its left.
	stack := []int{}
	for i := 0; i <= len(heights); i++ {
		// A height of 0 after the last bar closes every rectangle still open.
		height := 0
		if i < len(heights) {
			height = heights[i]
		}
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= height {
			// Measure the rectangle of the top bar's height that ends just before i.
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			left := -1
			if len(stack) > 0 {
				left = stack[len(stack)-1]
			}
			best = max(best, heights[top]*(i-left-1))
		}
		stack = append(stack, i)
	}
	return best
}

func main() {
	fmt.Println(largestRectangleArea([]int{2, 1, 5, 6, 2, 3}))    // 10
	fmt.Println(largestRectangleArea([]int{2, 4}))                // 4
	fmt.Println(largestRectangleArea([]int{6, 2, 5, 4, 5, 1, 6})) // 12
	fmt.Println(largestRectangleArea([]int{3, 3, 3}))             // 9
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Area of the largest rectangle that fits inside the histogram heights,
    // where every bar is 1 wide.
    public static int LargestRectangleArea(int[] heights)
    {
        int best = 0;
        // Bars whose rectangles are still growing to the right. Heights strictly
        // increase from bottom to top, so the bar under each one is the nearest
        // shorter bar on its left.
        var stack = new Stack<int>();
        for (int i = 0; i <= heights.Length; i++)
        {
            // A height of 0 after the last bar closes every rectangle still open.
            int height = i == heights.Length ? 0 : heights[i];
            while (stack.Count > 0 && heights[stack.Peek()] >= height)
            {
                // Measure the rectangle of the top bar's height that ends just before i.
                int top = stack.Pop();
                int left = stack.Count > 0 ? stack.Peek() : -1;
                best = Math.Max(best, heights[top] * (i - left - 1));
            }
            stack.Push(i);
        }
        return best;
    }

    public static void Main()
    {
        Console.WriteLine(LargestRectangleArea(new[] { 2, 1, 5, 6, 2, 3 })); // 10
        Console.WriteLine(LargestRectangleArea(new[] { 2, 4 })); // 4
        Console.WriteLine(LargestRectangleArea(new[] { 6, 2, 5, 4, 5, 1, 6 })); // 12
        Console.WriteLine(LargestRectangleArea(new[] { 3, 3, 3 })); // 9
    }
}

import java.util.ArrayDeque;

public class Solution {
    // Area of the largest rectangle that fits inside the histogram heights,
    // where every bar is 1 wide.
    static int largestRectangleArea(int[] heights) {
        int best = 0;
        // Bars whose rectangles are still growing to the right. Heights strictly
        // increase from bottom to top, so the bar under each one is the nearest
        // shorter bar on its left.
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i <= heights.length; i++) {
            // A height of 0 after the last bar closes every rectangle still open.
            int height = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] >= height) {
                // Measure the rectangle of the top bar's height that ends just before i.
                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;
    }

    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[] {2, 1, 5, 6, 2, 3})); // 10
        System.out.println(largestRectangleArea(new int[] {2, 4})); // 4
        System.out.println(largestRectangleArea(new int[] {6, 2, 5, 4, 5, 1, 6})); // 12
        System.out.println(largestRectangleArea(new int[] {3, 3, 3})); // 9
    }
}

Common Pitfalls

Pushing values when the answer needs a position or a distance. Push indices: a value is one lookup away, but a value alone can't tell you where it was.
Popping on the wrong comparison. For next greater, the new value settles the smaller ones, so pop while the top is smaller. Flipping it builds a stack sorted the other way and answers a different question.
Ignoring duplicates. Whether an equal value counts as an answer comes down to < versus <=, and the wording ("strictly warmer") tells you which.
Forgetting the elements still on the stack when the loop ends. They never found an answer, so they need a default, or a sentinel value that flushes them out as in the histogram.
Calling it O(n²) because of the nested loop. Count pushes and pops instead: each element gets at most one of each, so the total is O(n).