滑动窗口最大值

给定一个整数数组nums和一个整数k，请找出所有滑动窗口大小为k的子数组中的最大值。

题目描述：

给定一个整数数组nums和一个整数k，请你找出所有滑动窗口大小为k的子数组中的最大值。滑动窗口是一个固定大小的窗口，它通过在数组上滑动，每次滑动一个位置，来扫描数组中的元素。你需要返回每个滑动窗口中的最大值。

示例：

输入：nums = [1,3,-1,-3,5,3,6,7]，k = 3 输出：[3,3,5,5,6,7] 解释：滑动窗口的位置从左到右分别为：[1,3,-1]，[3,-1,-3]，[-1,-3,5]，[-3,5,3]，[5,3,6]，[3,6,7]。每个窗口中的最大值分别为3，3，5，5，6，7。

输入：nums = [1], k = 1 输出：[1]

解题步骤：

这个问题可以使用滑动窗口算法来解决。我们可以维护一个双端队列，队列中存储的是窗口内元素的索引。通过比较窗口内元素的值，我们可以找到每个窗口的最大值。

解题步骤如下：

1. 创建一个双端队列deque，用于存储窗口内元素的索引。

2. 初始化结果数组result为空数组，用于存储每个滑动窗口的最大值。

3. 初始化指针left和right，分别指向滑动窗口的左右边界。

4. 遍历整个数组nums，并执行以下操作：

   • 在每次遍历之前，检查队列的头部元素是否已经超出了当前窗口的范围，如果超出，则将其从队列中删除。

   • 检查当前遍历到的元素nums[i]与队列尾部元素所对应的元素nums[deque[rear]]的大小关系。如果nums[i]大于等于nums[deque[rear]]，则可以确定nums[deque[rear]]不会是任何窗口的最大值，因此将其从队列尾部删除，直到队列为空或者找到一个元素大于nums[i]。

   • 将当前元素的索引i添加到队列的尾部。

   • 如果窗口的起始位置（i-k+1）大于等于0，则将队列的头部元素nums[deque[front]]添加到结果数组result中，表示当前窗口的最大值。

5. 返回结果数组result。

JavaScript解题框架：

function maxSlidingWindow(nums, k) {
    let deque = []; // 双端队列
    let result = []; // 结果数组

    let left = 0;
    let right = 0;

    while (right < nums.length) {
        // 检查队列的头部元素是否已经超出了当前窗口的范围
        if (deque.length > 0 && deque[0] <= right - k) {
            deque.shift();
        }

        // 检查当前元素与队列尾部元素的大小关系
        while (deque.length > 0 && nums[right] >= nums[deque[deque.length - 1]]) {
            deque.pop();
        }

        // 将当前元素的索引添加到队列的尾部
        deque.push(right);

        // 如果窗口的起始位置大于等于0，则将队列的头部元素添加到结果数组中
        if (right >= k - 1

) {
            result.push(nums[deque[0]]);
        }

        right++;
    }

    return result;
}

在这个框架中，我们使用一个双端队列deque来存储窗口内元素的索引。我们还创建了一个结果数组result用于存储每个滑动窗口的最大值。

我们使用left和right两个指针来构建滑动窗口。在每次滑动窗口时，我们先检查队列的头部元素是否已经超出了当前窗口的范围，并进行相应的删除操作。然后，我们检查当前遍历到的元素与队列尾部元素的大小关系，进行元素的删除操作，直到队列为空或者找到一个元素大于当前元素。接着，将当前元素的索引添加到队列的尾部。如果窗口的起始位置大于等于0，则将队列的头部元素添加到结果数组中，表示当前窗口的最大值。