Largest Rectangle In Histogram: the idea to remember.

The core insight

Keep increasing bar heights with their earliest possible start index; finalize taller bars when a shorter bar arrives.

Why it works

The first shorter bar on the right closes the widest rectangle for each popped height. Its stored start captures its left boundary.

The mistake to avoid

Carry a popped bar's start into the new shorter bar, and process heights left in the stack after the scan.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Keep increasing bar heights with their earliest possible start index; finalize taller bars when a shorter bar arrives.
public int largestRectangleArea(int[] heights) {
  int area = 0, n = heights.length;
  int start;
  Stack<Pair<Integer,Integer>> stack = new Stack<>();
  for(int i=0;i<heights.length;i++){
     int curHt =heights[i];
     start = i;
    while(!stack.isEmpty() && stack.peek().getValue() > curHt){
      Pair<Integer,Integer> pair = stack.pop();
      int index = pair.getKey();
      int h = pair.getValue();
      area = Math.max(area, h * (i - index));
      start = index;
    }
    stack.push(new Pair(start,curHt));
  }

   while(!stack.isEmpty()){
      Pair<Integer,Integer> pair = stack.pop();
      int index = pair.getKey();
      int h = pair.getValue();
      area = Math.max(area, h * (n - index));
   }
    return area;
}

// Small standard-Java replacement for the platform Pair helper.
static class Pair<K,V> {
    final K key; final V value;
    Pair(K key,V value) { this.key=key; this.value=value; }
    K getKey() { return key; }
    V getValue() { return value; }
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection