带你读《图解算法小抄》二十、滑动窗口（2）

带你读《图解算法小抄》二十、滑动窗口（1）https://developer.aliyun.com/article/1348000?groupCode=tech_library

2）解题步骤：

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

解题步骤如下：

• 创建一个双端队列deque，用于存储窗口内元素的索引。
  
• 初始化结果数组result为空数组，用于存储每个滑动窗口的最大值。
  
• 初始化指针left和right，分别指向滑动窗口的左右边界。
  
• 遍历整个数组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中，表示当前窗口的最大值。
  

• 返回结果数组result。
  

3）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，则将队列的头部元素添加到结果数组中，表示当前窗口的最大值。

带你读《图解算法小抄》二十、滑动窗口（3）https://developer.aliyun.com/article/1347998?groupCode=tech_library