算法 滑动窗口最大值-(双指针+队列)

牛客网: BM45

题目: 数组num, 窗口大小size, 所有窗口内的最大值

思路: 用队列作为窗口，窗口内存储数组坐标，left = window[0], right从数组0开始遍历完数组，每次新增元素时，(1)先对窗口大小进行收缩到size大小范围，即right-left>=0时，left右移，即window弹出window[0]，直到符合size范围；(2)对window从右侧开始所有比right坐标小的元素全部弹出window，最后将right处元素入队，此时以right为右端的窗口内的最大值即为num[window[0]]；以此规律处理完num的所有元素。

注意: window进行收缩时要注意len(window)>0

代码:

// gopackage main
// import "fmt"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param num int整型一维数组 * @param size int整型 * @return int整型一维数组
*/
func maxInWindows( num []int ,  size int ) []int {// write code hereif len(num) < size || size == 0 || len(num) == 0 {return []int{}}res := []int{}window := []int{}for i := 0; i < size; i++ {for len(window) > 0 && num[window[len(window)-1]] < num[i] {window = window[:len(window)-1]}window = append(window, i)}res = append(res, num[window[0]])for i := size; i < len(num); i++ {for len(window)>0 && i - window[0] >= size {window = window[1:]}for len(window) > 0 && num[window[len(window)-1]] < num[i] {window = window[:len(window)-1]}window = append(window, i)res = append(res, num[window[0]])}return res
}