题目描述

给定一个数组 nums 和一个滑动窗口的大小 k，请找出所有滑动窗口里元素的最大值。

示例：

输入: nums = [1,3,-1,-3,5,3,6,7]，k = 3

输出: [3, 3, 5, 5, 6, 7]

解释：

• 第一个窗口是 [1, 3, -1]，最大值是 3。
• 第二个窗口是 [3, -1, -3]，最大值是 3。
• 第三个窗口是 [-1, -3, 5]，最大值是 5。
• 第四个窗口是 [-3, 5, 3]，最大值是 5。
• 第五个窗口是 [5, 3, 6]，最大值是 6。
• 第六个窗口是 [3, 6, 7]，最大值是 7。

PHP 示例代码

function maxSlidingWindow($nums, $k) {
    $window = new SplMaxHeap();
    $result = [];
    $left = 0;

    for ($right = 0; $right < count($nums); $right++) {
        // 维护窗口内最大堆
        if ($window->count() && $window->top() <= $left) {
            $window->extract(); // 移除窗口外的元素
        }
        $window->insert($nums[$right]);

        // 窗口形成
        if ($right - $left + 1 == $k) {
            $result[] = $window->top();
            $window->extract($nums[$left]); // 移除窗口左边界的元素
            $left++;
        }
    }

    return $result;
}

// 注意：PHP 标准库中没有直接的 Max Heap 实现，这里假设使用 SplMaxHeap 或自定义实现

Python 示例代码

from collections import deque

def maxSlidingWindow(nums, k):
    window = deque()
    result = []

    for i in range(len(nums)):
        # 移除窗口左边界比当前元素小的所有元素
        while window and nums[window[-1]] < nums[i]:
            window.pop()
        window.append(i)

        # 窗口形成
        if i >= k - 1:
            result.append(nums[window[0]])
            # 移除窗口左边界的索引
            if window[0] <= i - k:
                window.popleft()

    return result

# 示例调用
nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(maxSlidingWindow(nums, k))

JavaScript 示例代码

function maxSlidingWindow(nums, k) {
    const deque = [];
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        // 移除所有比当前元素小的元素
        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]]);

            // 移除窗口左边界的索引
            if (deque[0] <= i - k) {
                deque.shift();
            }
        }
    }

    return result;
}

// 示例调用
const nums = [1,3,-1,-3,5,3,6,7];
const k = 3;
console.log(maxSlidingWindow(nums, k));

码小课网站中有更多关于算法和数据结构的相关内容分享，欢迎大家学习交流。