### 题目描述补充 **题目：滑动窗口最大值** 给定一个数组 `nums` 和一个滑动窗口的大小 `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 ``` **要求**： - 你可以使用双端队列（deque）来解决这个问题，以便在 O(1) 时间复杂度内完成插入、删除和获取最大值的操作。 - 请使用 PHP、Python、JavaScript 编写你的解决方案。 ### 示例代码 #### PHP 示例 ```php function maxSlidingWindow($nums, $k) { $deque = new SplDoublyLinkedList(); // 使用 PHP 的双向链表模拟双端队列 $result = []; for ($i = 0; $i < count($nums); $i++) { // 移除窗口之外的元素 if (!$deque->isEmpty() && $deque->bottom() < $i - $k + 1) { $deque->shift(); } // 移除比当前元素小的元素，保证队列头部是最大值 while (!$deque->isEmpty() && $nums[$deque->top()] < $nums[$i]) { $deque->pop(); } $deque->push($i); // 插入当前元素的索引 // 当窗口形成后，开始记录结果 if ($i >= $k - 1) { $result[] = $nums[$deque->bottom()]; } } return $result; } ``` **注意**： PHP 标准库中没有直接的双端队列实现，这里使用 `SplDoublyLinkedList` 作为替代，并手动管理头部和尾部的操作。 #### Python 示例 ```python from collections import deque def maxSlidingWindow(nums, k): deque = deque() result = [] for i in range(len(nums)): # 移除窗口之外的元素 if deque and deque[0] == i - k: deque.popleft() # 移除比当前元素小的元素，保证队列头部是最大值 while deque and nums[deque[-1]] < nums[i]: deque.pop() deque.append(i) # 插入当前元素的索引 # 当窗口形成后，开始记录结果 if i >= k - 1: result.append(nums[deque[0]]) return result ``` #### JavaScript 示例 ```javascript function maxSlidingWindow(nums, k) { const deque = []; const result = []; for (let i = 0; i < nums.length; i++) { // 移除窗口之外的元素 if (deque.length > 0 && deque[0] === i - k) { deque.shift(); } // 移除比当前元素小的元素，保证队列头部是最大值 while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) { deque.pop(); } deque.push(i); // 插入当前元素的索引 // 当窗口形成后，开始记录结果 if (i >= k - 1) { result.push(nums[deque[0]]); } } return result; } ``` 以上代码均实现了滑动窗口的最大值查找，通过双端队列（deque）在 O(1) 时间复杂度内完成窗口内最大值的更新。