滑动窗口最大值

题解思路

这道题的核心是滑动窗口，需要找到每个窗口的最大值。我们可以使用 单调队列(双端队列) 来优化求解。

算法思路：

1. 维护一个双端队列 deque：

   • 存储数组的索引，而不是值，这样方便判断窗口是否过期。
   • 保证队列内索引对应的值单调递减（即队头最大）。

2. 窗口的滑动：

   • 每次新加入一个元素：
     • 先检查队头是否已经不在窗口范围内，如果是，则移除队头；
     • 再从队尾开始，移除所有比当前值小的元素，以保持单调递减；
     • 将当前索引加入队列；
   • 队头的元素即为当前窗口的最大值。

复杂度分析

• 时间复杂度：
  • 每个元素最多入队和出队各一次，故总时间复杂度为 $O(n)$。
• 空间复杂度：
  • 仅使用了双端队列，最坏情况下队列存储 k 个元素，故空间复杂度为 $O(k)$。

代码实现

Python代码：

from collections import deque
import sys

class Solution:
    def maxSlidingWindow(self, nums, k):
        deque_window = deque()  # 双端队列
        result = []
        
        for i in range(len(nums)):
            # 移除窗口左侧已过期的元素索引
            if deque_window and deque_window[0] < i - k + 1:
                deque_window.popleft()
            
            # 保持队列单调递减，移除所有小于当前元素的索引
            while deque_window and nums[deque_window[-1]] < nums[i]:
                deque_window.pop()
            
            # 添加当前元素索引
            deque_window.append(i)
            
            # 记录最大值（窗口形成后）
            if i >= k - 1:
                result.append(nums[deque_window[0]])

        return result

if __name__ == "__main__":
    # 读取输入
    n, k = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    
    # 计算滑动窗口最大值
    solution = Solution()
    result = solution.maxSlidingWindow(nums, k)
    
    # 输出结果
    print(" ".join(map(str, result)))

Java代码：

import java.util.*;
import java.io.*;

public class Main {
    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            Deque<Integer> deque = new LinkedList<>();
            int n = nums.length;
            int[] result = new int[n - k + 1];
            int index = 0;

            for (int i = 0; i < n; i++) {
                // 移除窗口外的元素
                if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                    deque.pollFirst();
                }

                // 维护单调递减队列
                while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                    deque.pollLast();
                }

                // 加入当前元素索引
                deque.offerLast(i);

                // 记录窗口最大值
                if (i >= k - 1) {
                    result[index++] = nums[deque.peekFirst()];
                }
            }

            return result;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] nk = reader.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);

        String[] numStr = reader.readLine().split(" ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(numStr[i]);
        }

        Main main = new Main();
        Solution solution = main.new Solution();
        int[] result = solution.maxSlidingWindow(nums, k);

        // 输出结果
        for (int i = 0; i < result.length; i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(result[i]);
        }
        System.out.println();
    }
}

C++代码：

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;  // 双端队列，存储索引
        
        for (int i = 0; i < nums.size(); i++) {
            // 移除窗口外的元素
            if (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }
            
            // 维护单调递减队列
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            
            // 加入当前元素索引
            dq.push_back(i);
            
            // 记录最大值
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        
        return result;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    Solution solution;
    vector<int> result = solution.maxSlidingWindow(nums, k);
    
    for (int i = 0; i < result.size(); i++) {
        if (i > 0) cout << " ";
        cout << result[i];
    }
    cout << endl;

    return 0;
}

Leetcode 11.滑动窗口的最大值-原题链接

题目内容

给你一个整数数组$nums$，有一个大小为 $k$的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 $k$个数字。滑动窗口每次只向右移动一位。

输出 滑动窗口中的最大值 。

输入描述

输入共两行。

• 第一行为两个个整数,$n，k$。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

如题，输出一行，数字之间以空格分隔。

样例1

输入

8 3
1 3 -1 -3 5 3 6 7

输出

3 3 5 5 6 7

说明

样例2

输入

1 1
1

输出

1

提示

• $1 <= nums.length <= 10^5$
• $-10^4 <= nums[i] <= 10^4$
• $1 <= k <= nums.length$