Skip to content

Instantly share code, notes, and snippets.

@alldroll
Created July 11, 2020 17:53
Show Gist options
  • Save alldroll/98295f55cf9eca44611046f68d6b358c to your computer and use it in GitHub Desktop.
Save alldroll/98295f55cf9eca44611046f68d6b358c to your computer and use it in GitHub Desktop.
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment