239. 滑动窗口最大值

leecode原题

题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例

示例 1:

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2:

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

解题思路

思路

我们设计一个单调队列, 队列有以下三个主要接口:

type MonotonicQueue interface{
//(滑动窗口中移除元素的数值)
//如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
Pop(value int) {}
//(滑动窗口添加元素的数值)
//如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
Push(value int)
// 获取队列队首元素
Front() int
}

每次队列随着滑动窗口的移动，保持一出、一进的原则，该单调队列中的队头元素就是最大值。

设计单调队列的时候，pop，和push操作要保持如下规则：

• pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
• push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
• 保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

实现

源码

// 单调队列
type MonotonicQueue struct {
    queue []int //使用数组实现队列功能
}

func NewMonotonicQueue() *MonotonicQueue {
    return &MonotonicQueue{queue: make([]int, 0)}
}

//(滑动窗口中移除元素的数值)
//如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
func (m *MonotonicQueue) Pop(value int) {
    if len(m.queue) > 0 && value == m.queue[0] {
        m.queue = m.queue[1:]
    }
}

//(滑动窗口添加元素的数值)
//如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
func (m *MonotonicQueue) Push(value int) {
    for len(m.queue) > 0 && value > m.queue[len(m.queue)-1] {
        m.queue = m.queue[:len(m.queue)-1]
    }
    // 添加到队尾
    m.queue = append(m.queue, value)
}

// 获取队列队首元素
func (m *MonotonicQueue) Front() int {
    if len(m.queue) > 0 {
        return m.queue[0]
    }
    return 0
}

// 滑动窗口最大值
func maxSlidingWindow(nums []int, k int) []int {
    numsLen := len(nums)
    maxArr := []int{}
    monotonicQueue := NewMonotonicQueue()
    // 先将第一个窗口元素全部塞入队列
    for i := 0; i < k; i++ {
        monotonicQueue.Push(nums[i])
    }
    maxArr = append(maxArr, monotonicQueue.Front())

    // 移动滑动窗口, 每次移动一位
    // 每次先优先级队列Pop出移除窗口的元素，然后在Push新进窗口的那个元素，最后获取此时窗口队首元素，即滑动窗口的最大值
    for i := k; i < numsLen; i++ {
        monotonicQueue.Pop(nums[i-k])
        monotonicQueue.Push(nums[i])
        maxArr = append(maxArr, monotonicQueue.Front())
    }
    return maxArr
}