原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-hard/xw4q0r/

解法一（python）：

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deq = deque()
        result = []
        
        for i in range(len(nums)):
            # 移除不在当前窗口的元素
            if deq and deq[0] == i - k:
                deq.popleft()
            
            # 移除所有比当前元素小的元素
            while deq and nums[deq[-1]] < nums[i]:
                deq.pop()
            
            # 添加当前元素索引到队列
            deq.append(i)
            
            # 当窗口形成时，将当前窗口的最大值添加到结果中
            if i >= k - 1:
                result.append(nums[deq[0]])
        
        return result

思路：

1. 初始化:

   • deq 是一个双端队列，用于存储窗口中元素的索引。
   • result 是一个列表，用于存储每个窗口的最大值。

2. 遍历数组:

   • 使用 for 循环遍历数组中的每个元素。

3. 维护窗口:

   • 如果 deq 的头部元素索引不在当前窗口内（即 i - k），则从 deq 中移除。
   • 从 deq 的尾部开始，移除所有比当前元素小的元素，因为它们不可能成为窗口的最大值。
   • 将当前元素的索引添加到 deq 的尾部。

4. 记录结果:

   • 当窗口的索引范围达到或超过 k-1 时，deq 的头部元素即为当前窗口的最大值，将其添加到 result 中。

解法二（java）：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 移除不在当前窗口的元素
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.pollFirst();
            }
            
            // 移除所有比当前元素小的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            // 添加当前元素索引到队列
            deque.offerLast(i);
            
            // 当窗口形成时，将当前窗口的最大值添加到结果中
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

思路：同解法一