Largest Rectangle in Histogram

Question

Given an array of bar heights representing a histogram, find the area of the largest rectangle that can be formed using these bars.

The bars have width 1, and you can combine adjacent bars if their heights allow it.

Example

Input:

heights = [3, 4, 9, 2, 7, 1]

Output: 10

Explanation:

The largest rectangle has height 2 and spans the first five bars: [3, 4, 9, 2, 7].
So area = 2 × 5 = 10.

Visual

My Notes

We use a stack to keep track of bars that are increasing in height.
Each element in the stack stores both height and width.
If the current bar is smaller than the one on top of the stack, we pop and merge widths to extend the rectangle backward.
After each step, we calculate the area using all stacked bars and keep the max.
This is a classic monotonic stack problem where we keep heights increasing and expand width when decreasing.

package main

import (
    "fmt"
)

type Node struct {
    h int
    w int
}

type Stack struct {
    items []Node
}

func (s *Stack) Top() Node {
    return s.items[len(s.items)-1]
}

func (s *Stack) Push(h int, w int) {
    s.items = append(s.items, Node{h, w})
}

func (s *Stack) Pop() {
    s.items = s.items[:len(s.items)-1]
}

func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}

func calculateArea(width int, stack *Stack, ans *int) {
    for i := 0; i < len(stack.items); i++ {
        area := stack.items[i].h * width
        if *ans < area {
            *ans = area
        }
        width -= stack.items[i].w
    }
}

func largestRectangleArea(heights []int) int {
    ans := 0
    stack := Stack{}

    for i, h := range heights {
        w := 1
        for !stack.IsEmpty() && stack.Top().h >= h {
            w += stack.Top().w
            stack.Pop()
        }
        stack.Push(h, w)
        calculateArea(i+1, &stack, &ans)
    }

    return ans
}

func main() {
    result := largestRectangleArea([]int{3, 4, 9, 2, 7, 1})
    fmt.Println(result)
}