leetcode-go/leetcode/hard/239.sliding-window-maximum.go

import (
	"container/list"
)

func maxSlidingWindow(nums []int, k int) (ans []int) {
	n := len(nums)
	if n <= 1 || k == 1 {
		return nums
	}
	l := list.New()
	l.PushBack(0)
	for i := 1; i < n; i++ {
		if front := l.Front(); front.Value.(int) <= i-k {
			l.Remove(front)
		}
		for back := l.Back(); back != nil && nums[back.Value.(int)] <= nums[i]; back = l.Back() {
			l.Remove(back)
		}
		l.PushBack(i)
		if k-1 <= i {
			ans = append(ans, nums[l.Front().Value.(int)])
		}
	}
	return
}

func maxSlidingWindowSlow(nums []int, k int) (ans []int) { // If use BST, O(nlog(k))
	n := len(nums) // Actually, just abit slower.
	if n <= 1 || k == 1 {
		return nums
	}
	var sl SortedList
	for i := 0; i < n; i++ {
		if k <= i {
			ans = append(ans, sl.Max())
			sl.Delete(nums[i-k])
		}
		sl.Insert(nums[i])
	}
	return append(ans, sl.Max())
}

type SortedList struct {
	List []int
	Len  int
}

func (sl SortedList) Max() int {
	return sl.List[sl.Len-1]
}

func (sl SortedList) Search(x int) int {
	beg, end := 0, sl.Len
	for beg < end {
		mid := beg + (end-beg)/2
		if x < sl.List[mid] {
			end = mid
		} else if sl.List[mid] < x {
			beg = mid+1
		} else {
			return mid
		}
	}
	return beg
}

func (sl *SortedList) Insert(x int) {
	idx := sl.Search(x)
	sl.List = append(sl.List, 0)
	copy(sl.List[idx+1:], sl.List[idx:])
	sl.List[idx] = x
	sl.Len++
}

func (sl *SortedList) Delete(x int) {
	idx := sl.Search(x)
	copy(sl.List[idx:], sl.List[idx+1:])
	sl.Len--
	sl.List = sl.List[:sl.Len]
}