https://leetcode.com/problems/largest-rectangle-in-histogram/

largest-rectangle-in-histogram.go

import "container/heap"

type HeapItem struct {
    val int
    index int
}

type Heap []HeapItem

func (h Heap) Len() int { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i].val > h[j].val }
func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *Heap) Push(x interface{}) { *h = append(*h, x.(HeapItem)) }

func (h *Heap) Pop() interface{} {
    n := h.Len()
    old := *h
    x := old[n - 1]
    *h = old[:n - 1]
    
    return x
}

func largestRectangleArea(heights []int) int {
    h := Heap{}
    
    for i, val := range heights {
        h.Push(HeapItem{
            val: val,
            index: i,
        })
    }
    
    heap.Init(&h)
    visited := make([]bool, len(heights))
    area := 0
    
    for h.Len() > 0 {
        item := heap.Pop(&h).(HeapItem)
        
        if visited[item.index] {
            continue
        }
        
        width := expand(heights, visited, item.index)
        area = max(area, width * item.val)
    }
    
    return area
}

func expand(arr []int, visited []bool, k int) int {
    i, j := k, k + 1
    length := 0
    
    for {
        prev := length
        
        if i >= 0 && arr[i] >= arr[k] {
            visited[i] = true
            length++
            i--
        }
        
        if j < len(arr) && arr[j] >= arr[k] {
            visited[j] = true
            length++
            j++
        }
        
        if prev == length {
            break
        }
    }
    
    return length
}

func max(a, b int) int {
    if a < b {
        return b
    }
    
    return a
}