8.25数组滑动窗口最值 - WisperDin/blog GitHub Wiki

描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3

那么一共存在6个滑动窗口, 他们的最大值分别为{4,4,6,6,6,5}；

针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个 {[2,3,4],2,6,2,5,1}，最大值4 {2,[3,4,2],6,2,5,1}，最大值4 {2,3,[4,2,6],2,5,1}，最大值6 {2,3,4,[2,6,2],5,1}，最大值6 {2,3,4,2,[6,2,5],1}，最大值6 {2,3,4,2,6,[2,5,1]}，最大值5

思路

可以使用队列，描述滑动窗口这个先进先出的模型，问题转化成，求队列中的最大值

假设从第一个窗口开始，一直往后滑动，往队列加入新元素时：

• 将当前队列中比新元素小的元素pop
• 将不属于当前窗口的元素pop出

通过这种方式，使得队列的队首始终是当前窗口的最大值

实现

package ShiftWindows

import (
	"container/list"
)


func ShiftWindows(arr []int, size int) []int {
	if size<=0 {
		return nil
	}
	if len(arr)<size {
		return nil
	}

	q:=list.New()

	//first windows
	for i:=0;i<size;i++{
		if q.Len()!=0 && arr[i]>= arr[q.Back().Value.(int)] {
			q.Remove(q.Back())
		}
		q.PushBack(i)
	}

	ans := []int{}

	//next windows
	for i:=size ; i< len(arr) ; i++ {
		//每次循环都是在考察一个窗口的最值， i 为该窗口的最后一个元素位置
		//1. pop-tail 队列中比当前值要小的元素 for
		//2. pop-front 队列中不属于当前窗口的元素 if
		//3. push当前元素
		//根据1,2 每次执行后的队首都是当前窗口的最大元素

		//当前队首为上一个窗口的最值
		ans = append(ans, arr[q.Front().Value.(int)])

		//从队尾开始考察是否有比当前值要小的元素，有则pop
		for q.Len()!=0 && arr[i]>= arr[q.Back().Value.(int)] {
			q.Remove(q.Back())
		}

		//删除队列中比当前考察值要大且在窗口外的元素
		//上一个窗口最值位置 不在本次搜索最值的窗口内
		if q.Len()!=0 && q.Front().Value.(int) < i-size+1{
			q.Remove(q.Front())
		}

		q.PushBack(i)
	}
	//最后一个结果
	ans = append(ans, arr[q.Front().Value.(int)])
	return ans
}