Claude
b9aeb78b24
Co-Authored-By: Claude Sonnet 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_017ic4b6nxynun5JFivebVb1
26 lines
1.2 KiB
Plaintext
26 lines
1.2 KiB
Plaintext
Largest rectangle in a histogram: pops, widths and areas
|
|
========================================================
|
|
|
|
heights [2, 1, 5, 6, 2, 3]
|
|
i=0 height=2:
|
|
push index 0 stack(top first) = [0]
|
|
i=1 height=1:
|
|
pop bar of height 2: left edge index -1, right edge index 0, width 1, area 2 best = 2
|
|
push index 1 stack(top first) = [1]
|
|
i=2 height=5:
|
|
push index 2 stack(top first) = [2, 1]
|
|
i=3 height=6:
|
|
push index 3 stack(top first) = [3, 2, 1]
|
|
i=4 height=2:
|
|
pop bar of height 6: left edge index 2, right edge index 3, width 1, area 6 best = 6
|
|
pop bar of height 5: left edge index 1, right edge index 3, width 2, area 10 best = 10
|
|
push index 4 stack(top first) = [4, 1]
|
|
i=5 height=3:
|
|
push index 5 stack(top first) = [5, 4, 1]
|
|
i=6 (sentinel) height=0:
|
|
pop bar of height 3: left edge index 4, right edge index 5, width 1, area 3 best = 10
|
|
pop bar of height 2: left edge index 1, right edge index 5, width 4, area 8 best = 10
|
|
pop bar of height 1: left edge index -1, right edge index 5, width 6, area 6 best = 10
|
|
push index 6 stack(top first) = [6]
|
|
largest rectangle = 10
|