PHP滑动窗口最大值算法解析

本文深入解析了PHP中高效实现滑动窗口最大值的经典算法——利用双端队列维护单调递减的下标序列，确保队首始终指向当前窗口的最大值索引，以O(n)时间复杂度和O(k)空间复杂度突破暴力解法瓶颈；文章不仅提供健壮、可直接运行的SplDoublyLinkedList实现，还剖析了下标存储、过期清理与弱值淘汰的关键逻辑，并对比了数组模拟方案的取舍，辅以详尽边界案例和易错点提醒，让读者既能掌握原理内核，又能写出生产级可靠代码。

PHP 实现滑动窗口最大值，核心是用双端队列（deque）维护窗口内可能成为最大值的元素下标，保证队首始终是当前窗口的最大值索引。时间复杂度 O(n)，空间复杂度 O(k)。

算法思路：单调递减双端队列

不直接存数值，而是存数组下标，便于判断是否滑出窗口。队列保持「从头到尾对应值严格递减」：

• 新元素入队前，从队尾开始弹出所有 ≤ 当前值的下标（它们不可能再成为后续窗口最大值）
• 检查队首下标是否已小于窗口左边界，若是则从队首弹出（过期淘汰）
• 当窗口形成（即 i ≥ k−1）后，每次取队首下标对应的值作为当前窗口最大值

PHP 代码实现（使用 SplDoublyLinkedList 模拟 deque）

PHP 原生无内置 deque，可用 SplDoublyLinkedList 替代，注意启用双端操作：

function maxSlidingWindow($nums, $k) {
    if (empty($nums) || $k  count($nums)) {
        return [];
    }
$deque = new SplDoublyLinkedList();
$deque->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);

$result = [];

for ($i = 0; $i < count($nums); $i++) {
    // 1. 移除队尾所有小于等于当前数的下标（维持递减）
    while (!$deque->isEmpty() && $nums[$deque->top()] <= $nums[$i]) {
        $deque->pop();
    }
    // 2. 加入当前下标
    $deque->push($i);

    // 3. 移除队首过期下标（超出窗口左边界）
    $leftBound = $i - $k + 1;
    while (!$deque->isEmpty() && $deque->bottom() < $leftBound) {
        $deque->shift();
    }

    // 4. 窗口成型后记录最大值（队首对应值）
    if ($i >= $k - 1) {
        $result[] = $nums[$deque->bottom()];
    }
}

return $result;
}
// 示例调用
$nums = [1, 3, -1, -3, 5, 3, 6, 7];
$k = 3;
print_r(maxSlidingWindow($nums, $k));
// 输出: [3, 3, 5, 5, 6, 7]

关键细节说明

避免常见错误，需注意：

• 下标比较而非值比较：队列中只存下标，所有大小判断都基于 $nums[$index]
• 队首淘汰时机：必须在每轮末尾（或记录答案前）检查过期，不能只在入队时处理
• 空队列保护：每次调用 bottom()、top()、shift()、pop() 前务必用 isEmpty() 判断
• 边界情况覆盖：k=1、k=数组长度、空数组、k大于数组长度等均应返回合理结果（如空数组）

替代方案：纯数组模拟（更直观易懂）

若不想依赖 SPL，可用 PHP 数组 + array_shift() 和 array_pop() 模拟，但注意 array_shift() 是 O(n)，整体退化为 O(nk)；适合小数据或教学演示：

// 简化版（仅作理解，非高性能推荐）
function maxSlidingWindowSimple($nums, $k) {
    $deque = []; // 存下标
    $result = [];
for ($i = 0; $i < count($nums); $i++) {
    while (!empty($deque) && $nums[end($deque)] <= $nums[$i]) {
        array_pop($deque);
    }
    $deque[] = $i;

    if ($deque[0] < $i - $k + 1) {
        array_shift($deque);
    }

    if ($i >= $k - 1) {
        $result[] = $nums[$deque[0]];
    }
}

return $result;
}

不复杂但容易忽略：队列里存的是下标，不是值；窗口左边界是 i − k + 1，不是 i − k；每次循环都要清理过期和弱值，顺序不能颠倒。

以上就是《PHP滑动窗口最大值算法解析》的详细内容，更多关于的资料请关注golang学习网公众号！