滑动窗口最大值问题用单调双端队列在o(n)时间内求解，php用数组模拟deque：维护索引队列保证单调递减且队首有效，避免o(n×k)暴力遍历。
滑动窗口最大值问题，核心是用单调队列（通常是双端队列）在 O(n) 时间内高效维护窗口内的最大值，避免对每个窗口都重新遍历找最大——PHP 中虽无原生 deque，但可用数组模拟，关键在于保持队列单调递减且只存索引。
为什么不用 max() 遍历窗口？
暴力法对每个长度为 k 的窗口调用 max(array_slice($nums, $i, $k))，时间复杂度达 O(n×k)，当 n 和 k 都很大时明显超时。而滑动窗口算法将均摊时间降到 O(1) 每元素，总时间 O(n)。
用数组模拟单调递减双端队列
PHP 数组支持 array_shift()（头删）、array_pop()（尾删）、array_push()（尾增），足够模拟 deque 行为。我们维护一个索引队列 $deque，保证：
- 队首索引始终在当前窗口内（需检查是否过期）
- 队列中对应元素严格单调递减（即 $nums[$deque[0]] > $nums[$deque[1]] > ...）
- 新元素入队前，从队尾弹出所有 ≤ 它的元素（破坏单调性）
完整可运行 PHP 实现
// 输入：整数数组 $nums，窗口大小 $k
// 输出：每个窗口的最大值组成的数组
function maxSlidingWindow($nums, $k) {
$n = count($nums);
if ($n === 0 || $k === 0 || $k > $n) return [];
$deque = []; // 存索引，非数值
$result = [];
// 初始化第一个窗口
for ($i = 0; $i
while (!empty($deque) && $nums[end($deque)]
array_pop($deque);
}
array_push($deque, $i);
}
$result[] = $nums[$deque[0]]; // 第一个窗口最大值
// 滑动剩余窗口
for ($i = $k; $i
// 移除已滑出窗口的队首索引
if ($deque[0] === $i - $k) {
array_shift($deque);
}
// 维护单调性：从队尾踢掉 ≤ 当前值的索引
while (!empty($deque) && $nums[end($deque)]
array_pop($deque);
}
array_push($deque, $i);
$result[] = $nums[$deque[0]];
}
return $result;
}
关键细节与易错点
- 存索引而非值：便于判断队首是否越界（$deque[0] === $i - $k），也避免相同值无法区分位置
- 边界检查要前置：每次新窗口开始前先移除过期索引，再处理当前元素，顺序不能反
- 单调性判断用 ≤ 而非 ：遇到相等值也要弹出旧索引，保证队列严格递减，否则可能残留无效大索引
- 初始化阶段不可省略：前 k 个元素必须走一遍入队逻辑，不能直接取 max
