239. 滑动窗口最大值

这段代码是 滑动窗口最大值 问题的高效解决方案，使用了 单调队列 数据结构，时间复杂度为 (O(n))。
下面逐步解释代码的设计思想和运行机制：

问题描述

给定一个数组 nums 和一个窗口大小 k，要求滑动窗口每次向右移动一格，计算每个窗口中的最大值。

代码解析

1. MyQueue 类：实现单调队列

单调队列是该解法的核心数据结构，确保队列中的元素是单调递增或递减的。这里实现了单调递减队列（从大到小排序）。

MyQueue 的三个关键函数：

1. pop(int value)：移除队列前端元素

   • 当队列非空且队列首元素等于待移除的值时，将队列首元素弹出。
   • 这是为了实现滑动窗口的「移除最前面的元素」。

2. push(int value)：添加新元素

   • 如果新元素大于队列尾部元素，就不断将尾部元素弹出，直到队列为空或队列尾部元素大于等于新元素。
   • 这样保持队列从大到小的单调顺序。
   • 最终，将新元素添加到队列尾部。

3. front()：返回当前队列的最大值

   • 队列的前端（front）始终保存着当前滑动窗口中的最大值。

2. 滑动窗口的具体实现

初始化阶段

1. 将前 (k) 个元素依次加入到 MyQueue 中。
   • 这时 MyQueue 已经维护了一个大小为 (k) 的滑动窗口，并且最大值在队列前端。

滑动窗口阶段

从第 (k) 个元素开始向右滑动，重复以下三步操作：

1. 移除最前面的元素

   que.pop(nums[i - k]);
   

   • 移除「窗口的起始位置」元素（nums[i-k]）。
   • 如果这个元素正好是队列的最大值（队首元素），pop 函数会将其从队首移除。

2. 加入新的元素

   que.push(nums[i]);
   

   • 将当前元素 nums[i] 加入队列，并确保队列依然是单调递减的。

3. 记录当前窗口的最大值

   result.push_back(que.front());
   

   • 队首元素 que.front() 就是当前滑动窗口的最大值。

代码执行流程举例

输入：

nums = [1,3,-1,-3,5,3,6,7], k = 3

执行过程：

关键问题解答

1. 为什么单调队列能保证最大值？

   • 当新元素 nums[i] 加入时，队尾的元素如果小于它，就会被弹出。
   • 因此，队列中元素始终是从大到小排列的，队首元素一定是最大值。

2. 为什么时间复杂度是 (O(n))？

   • 每个元素最多被 push 和 pop 操作一次，deque 的 push_back 和 pop_front 操作都是 (O(1))。
   • 因此，总时间复杂度为 (O(n))。

3. 空间复杂度是多少？

   • 使用了一个单调队列，最多存储 (k) 个元素。
   • 所以空间复杂度是 (O(k))。

if (!que.empty() && value == que.front()) 这行代码中的 !que.empty() 是必要的，不能去掉。

原因分析：

1. que.front() 的前提：
   • que.front() 用于访问队首元素。
   • 如果队列为空时直接调用 que.front()，会导致未定义行为，程序可能崩溃。
2. if 条件的逻辑：
   • !que.empty() 确保队列中至少有一个元素。
   • 只有队列不为空时，才可以安全地比较 value == que.front()。