104 lines
1.8 KiB
Go
104 lines
1.8 KiB
Go
package main
|
|
|
|
type Window struct {
|
|
nums []int
|
|
begin int
|
|
end int
|
|
size int
|
|
numsCount int
|
|
}
|
|
|
|
func (w *Window) Next() *Window {
|
|
if w.end+1 >= w.numsCount {
|
|
return nil
|
|
}
|
|
w.begin++
|
|
w.end++
|
|
return w
|
|
}
|
|
|
|
func (w *Window) InWindow(index int) bool {
|
|
return (index >= w.begin) && (index <= w.end)
|
|
}
|
|
|
|
func maxBruteForce(nums []int, begin int, end int) WindowMaximum {
|
|
max := nums[begin]
|
|
index := begin
|
|
for i := begin + 1; i <= end; i++ {
|
|
if nums[i] > max {
|
|
max = nums[i]
|
|
index = i
|
|
}
|
|
}
|
|
|
|
return WindowMaximum{index: index, value: max, valid: true}
|
|
}
|
|
|
|
func (w *Window) Max(prevMax WindowMaximum) WindowMaximum {
|
|
if !prevMax.valid {
|
|
return maxBruteForce(w.nums, w.begin, w.end)
|
|
}
|
|
|
|
if w.nums[w.begin-1] == w.nums[w.begin] {
|
|
if w.nums[w.end-1] == w.nums[w.end] {
|
|
return prevMax
|
|
} else {
|
|
if w.nums[w.end] >= prevMax.value {
|
|
return WindowMaximum{value: w.nums[w.end], valid: true, index: w.end}
|
|
}
|
|
}
|
|
} else {
|
|
if w.nums[w.end-1] == w.nums[w.end] {
|
|
if w.nums[w.begin] >= prevMax.value {
|
|
return WindowMaximum{value: w.nums[w.begin], valid: true, index: w.begin}
|
|
}
|
|
}
|
|
}
|
|
|
|
if !w.InWindow(prevMax.index) {
|
|
return maxBruteForce(w.nums, w.begin, w.end)
|
|
}
|
|
|
|
if w.nums[w.end] >= prevMax.value {
|
|
return WindowMaximum{value: w.nums[w.end], valid: true, index: w.end}
|
|
}
|
|
|
|
return prevMax
|
|
}
|
|
|
|
func NewWindow(nums []int, k int) *Window {
|
|
w := Window{}
|
|
w.nums = nums
|
|
w.size = k
|
|
w.numsCount = len(nums)
|
|
w.begin = 0
|
|
w.end = k - 1
|
|
|
|
if w.end < 0 {
|
|
return nil
|
|
}
|
|
if k > w.numsCount {
|
|
return nil
|
|
}
|
|
|
|
return &w
|
|
}
|
|
|
|
type WindowMaximum struct {
|
|
index int
|
|
value int
|
|
valid bool
|
|
}
|
|
|
|
func MaxSlidingWindow(nums []int, k int) []int {
|
|
maximums := []int{}
|
|
var max WindowMaximum
|
|
|
|
for w := NewWindow(nums, k); w != nil; w = w.Next() {
|
|
max = w.Max(max)
|
|
maximums = append(maximums, max.value)
|
|
}
|
|
|
|
return maximums
|
|
}
|