package slidingwindowmaximum

import (
	"container/heap"
)

// 239. 滑动窗口最大值
// https://leetcode-cn.com/problems/sliding-window-maximum/

// 堆、优先队列
// 懒惰删除法

type IndexIntHead [][2]int // 0 = index , 1 = value

func (iih IndexIntHead) Len() int {
	return len(iih)
}

func (iih IndexIntHead) Less(i, j int) bool {
	return iih[i][1] > iih[j][1]
}

func (iih IndexIntHead) Swap(i, j int) {
	iih[i], iih[j] = iih[j], iih[i]
}

func (iih *IndexIntHead) Pop() interface{} {
	old := *iih
	n := len(old)
	x := old[n-1]
	*iih = old[0 : n-1]
	return x
}

func (h *IndexIntHead) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func maxSlidingWindow(nums []int, k int) []int {
	q := &IndexIntHead{}
	for i := 0; i < k; i++ {
		*q = append(*q, [2]int{i, nums[i]})
	}
	heap.Init(q)

	n := len(nums)
	res := make([]int, 0, n-k+1)
	res = append(res, (*q)[0][1])

	for i := k; i < n; i++ {
		heap.Push(q, [2]int{i, nums[i]})
		for (*q)[0][0] <= i-k {
			heap.Pop(q)
		}
		res = append(res, (*q)[0][1])
	}
	return res
}

// 暴力解法，超过是时间限制
// func maxSlidingWindow(nums []int, k int) []int {
// 	res := make([]int, 0, k)
// 	l := len(nums)

// 	for i := 0; i <= l-k; i++ { // nums[i:k+i]
// 		max := nums[i]
// 		for j := 1; j < k; j++ {
// 			if max < nums[i+j] {
// 				max = nums[i+j]
// 			}
// 		}
// 		res = append(res, max)
// 	}
// 	return res
// }