题目链接
题目描述:
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
解题思路
本题的关键在于如何从滑动窗口中动态获取每一个最大值。这里我们可以考虑维护一个单调队列,简而言之就是始终保证队列中的元素均处在当前滑动窗口范围内且元素由队头至队尾呈单调递减的状态。那么这个单调队列需要什么操作呢?
- 队尾插入当前元素;
- 队头弹出最大值,原因在于单调队列的队头元素一定是当前滑动窗口的最大值;
- 队尾弹出元素,原因在于为维持单调队列的单调性(递减),要先判断待插入元素与队尾元素的大小关系,如果待插入元素大于队尾元素,说明队尾元素肯定不会是滑动窗口的最大值,所以要先将队尾元素弹出再将插入元素进队;
- 队头弹出已经不属于当前滑动窗口范围的元素。为什么会从队头弹出而不会从队尾弹出不属于窗口的元素?原因在于上一个队尾弹出操作中,为了维持单调性,不可能成为最大值的元素早已经被弹出,所以说剩下可能需要弹出的元素只有队头的窗口最大元素。同时也可以保证最大值的实时更新,如果没有这一步操作,当遇到整个数组的最大值时,滑动窗口的最大值肯定不会再变化(甚至不用等到那时候,超出窗口大小的一定范围内的数组最大值也会导致滑动窗口最大值在那一段时间不变)。
由上述操作我们发现队头队尾均需要弹出元素,为应对这些问题,我们可以考虑使用双端队列deque
数据结构(c++ stl
)。
代码
cpp
1 | class Solution { |
如果有错误或者不严谨的地方,请务必给予指正,十分感谢。