题解 | #滑动窗口的最大值#

package main

type Heap struct {
	data  []int
	n     int
	count int
}

func newHeap(n int) Heap {
	return Heap{
		data:  make([]int, n+1),
		n:     n,
		count: 0,
	}
}

func (h *Heap) Insert(data int) {
	if h.count >= h.n {
		return
	}
	h.count++
	h.data[h.count] = data
	i := h.count
	h.heapify2(i)
}

func (h *Heap) heapify2(i int) {
	for i/2 > 0 && h.data[i] > h.data[i/2] {
		h.data[i], h.data[i/2] = h.data[i/2], h.data[i]
		i /= 2
	}
}

func (h *Heap) getMax() int {
	return h.data[1]
}

func (h *Heap) remove(v int) {
	vI := 0
	for i := 1; i <= h.count; i++ {
		if h.data[i] == v {
			vI = i
			break
		}
	}
	h.data[vI] = h.data[h.count]
	if h.data[h.count] > v {
		h.heapify2(vI)
	}
	if h.data[h.count] < v {
		h.heapify(vI)
	}
	h.count--
}

func (h *Heap) heapify(i int) {

	for {
		maxPos := i
		if i*2 <= h.n && h.data[i] < h.data[i*2] {
			maxPos = 2 * i
		}
		if i*2+1 <= h.n && h.data[maxPos] < h.data[2*i+1] {
			maxPos = 2*i + 1
		}
		if maxPos == i {
			break
		}
		h.data[maxPos], h.data[i] = h.data[i], h.data[maxPos]
		i = maxPos
	}
}

func maxInWindows(num []int, size int) []int {
	if len(num) < size || size == 0 {
		return []int{}
	}
	if size == 1 {
		return num
	}
	heap := newHeap(size)
	max := []int{}
	for i := 0; i < size; i++ {
		heap.Insert(num[i])
	}
	max = append(max, heap.getMax())
	for i := size; i < len(num); i++ {
		heap.remove(num[i-size])//删除过期元素
		heap.Insert(num[i])//插入当前元素
		max = append(max, heap.getMax())//获取堆顶元素

	}
	return max
}