package main

import "container/heap"

type pair struct {
	value, idx int
}

type pairs []pair

func (p pairs) Len() int {
	return len(p)
}

// 大根堆
func (p pairs) Less(i, j int) bool {
	return p[i].value > p[j].value
}

func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p *pairs) Pop() interface{} {
	n := p.Len()
	t := (*p)[n-1]
	*p = (*p)[:n-1]
	return t
}

func (p *pairs) Push(x interface{}) {
	(*p) = append((*p), x.(pair))
}

// [1, -1]   1
func maxSlidingWindow(nums []int, k int) []int {
	n := len(nums)
	res := []int{}
	if k == 0 {
		res := make([]int, n, n)
		return res
	}
	// 初始化堆
	pHeap := make(pairs, 0, 0)
	heap.Init(&pHeap)
	for i := 0; i < k; i++ {
		heap.Push(&pHeap, pair{nums[i], i})
	}
	res = append(res, pHeap[0].value)
	for i := 1; i+k-1 < n; i++ {
		for pHeap.Len() > 0 && pHeap[0].idx < i {
			heap.Pop(&pHeap)
		}
		heap.Push(&pHeap, pair{nums[i+k-1], i + k - 1})
		res = append(res, pHeap[0].value)
	}
	return res
}

func main() {

}