package main
import (
"fmt"
)
func main() {
nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
fmt.Println(maxSlidingWindow(nums, 3))
}
func maxSlidingWindow(nums []int, k int) []int {
if nums == nil || len(nums) == 0 {
return []int{}
}
res := make([]int, 0)
window := make([]int, 0)
for i, x := range nums {
if i >= k && window[0] <= i-k {
// 如果 当前坐标 >= k ,并且当前队列顶部坐标, 超过了窗口的左界, 移除掉
window = window[1:]
}
for len(window) > 0 && nums[window[len(window)-1]] <= x {
// 对新进入的元素 x,遍历进行对比,如果队列中右边的元素小于等于 x, 则移除掉
window = window[:len(window)-1]
}
// 推入当前值的下标
window = append(window, i)
if i >= k-1 {
// 结果加入 result
res = append(res, nums[window[0]])
}
}
return res
}
package main
import (
"fmt"
)
func main() {
nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
fmt.Println(maxSlidingWindow(nums, 3))
}
func maxSlidingWindow(nums []int, k int) []int {
if nums == nil || len(nums) == 0 {
return []int{}
}
res := make([]int, 0)
window := Queue{}
for i, x := range nums {
if i >= k && window.LPeek() <= i-k {
window.LPop()
}
for window.Len() > 0 && nums[window.RPeek()] <= x {
window.RPop()
}
window.RPush(i)
if i >= k-1 {
res = append(res, nums[window.LPeek()])
}
}
return res
}
type Queue struct {
data []int
}
func (this *Queue) Len() int {
return len(this.data)
}
func (this *Queue) LPush(i int) {
this.data = append([]int{i}, this.data...)
}
func (this *Queue) RPush(i int) {
this.data = append(this.data, i)
}
func (this *Queue) LPop() int {
i := this.data[0]
this.data = this.data[1:]
return i
}
func (this *Queue) RPop() int {
i := this.data[len(this.data)-1]
this.data = this.data[:len(this.data)-1]
return i
}
func (this *Queue) LPeek() int {
return this.data[0]
}
func (this *Queue) RPeek() int {
return this.data[len(this.data)-1]
}