笔试时间：2024年05月08日

历史笔试传送门：2023秋招笔试合集

第一题

题目

给定一个长度为n的整数数组，大小为k的滑动窗口从数组的最左侧移动到数组的最右侧，滑动窗口每次只向右移动一位。请使用一次数组遍历，输出每个滑动窗口中的最大值。

输入描述

第一行为，正整数n和正整数k，k<=n；第二行为，n个整数。

输出描述

每个滑动窗口的最大值依次输出，空格分隔。

样例输入一

100 80

209 928 234 9 390 809 34 458 826 851 929 954 228 508 87

839 756 900 461 696 916 880 293 501 770 339 188 592 75

126 245 509 526 235 634 440 246 277 579 687 595 914 873

130 335 811 818 718 78 540 367 330 742 973 29 250 834 656

725 686 451 249 683 895 172 790 180 378 715 436 522 178

370 521 698 662 167 606 198 635 27 538 840 670 829 735

932 621 910 700 348 857 319 556 591 384 942 947 523 14

样例输出一

973 973 973 973 973 973 973 973 973 973 973 973 973 973 973 973 973 973 973 973 973

样例输入二

100 10

534 560 153 216 972 259 908 429 809 353 735 463 898 750

814 420 337 296 71 518 795 377 407 964 407 895 747 242

170 929 779 607 281 305 168 105 22 153 742 62 617 157 199

201 573 223 918 462 972 889 644 132 970 227 888 388 499

975 752 927 382 445 861 883 133 738 467 987 145 480 95

698 735 605 395 684 389 450 211 331 306 14 428 507 423

934 505 186 526 238 289 175 307 158 157 718 468 858 949

986

样例输出二

972 972 972 972 972 908 908 898 898 898 898 898 898 814 964 964 964 964 964 964 964 964 964 964 929 929 929 929 929 929 779 742 742 742 742 742 742 918 918 972 972 972 972 972 972 972 972 972 975 975 975 975 975 975 975 975 975 975 987 987 987 987 987 987 987 987 987 987 735 735 735 735 735 684 684 684 934 934 934 934 934 934 934 934 934 934 718 718 858 949 986

参考题解

Leetcode原题，使用了单调队列（双端队列）来解决这个问题，这段代码使用了单调队列（双端队列）来解决滑动窗口的最大值问题。时间复杂度为O(n)，只需要一次数组遍历。

C++：[此代码未进行大量数据的测试，仅供参考]

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

using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    if (nums.empty() || k <= 0) {
        return {};
    }
    
    int n = nums.size();
    vector<int> result;
    deque<int> deque;
    
    for (int i = 0; i < n; i++) {
        // 保持窗口大小不超过k
        while (!deque.empty() && deque.front() < i - k + 1) {
            deque.pop_front();
        }
        
        // 删除队列中小于当前元素的值
        while (!deque.empty() && nums[deque.back()] < nums[i]) {
            deque.pop_back();
        }
        
        // 将当前元素加入队列尾部
        deque.push_back(i);
        
        // 记录窗口中的最大值
        if (i >= k - 1) {
            result.push_back(nums[deque.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];
    }
    
    vector<int> result = maxSlidingWindow(nums, k);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << " ";
        }
    }
    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class SlidingWindowMax {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取数组长度n和滑动窗口大小k
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        
        // 读取整数数组
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        // 输出滑动窗口的最大值
        int[] result = maxSlidingWindow(nums, k);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) {
                System.out.print(" ");
            }
        }
        
        scanner.close();
    }
    
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        
        int index = 0;
        for (int i = 0; i < n; i++) {
            // 保持窗口大小不超过k
            while (!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;
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

from collections import deque

def max_sliding_window(nums, k):
    if not nums or k <= 0:
        return []
    
    n = len(nums)
    result = []
    deque = deque()
    
    for i in range(n):
        # 保持窗口大小不超过k
        if deque and deque[0] < i - k + 1:
            deque.popleft()
        
        # 删除队列中小于当前元素的值
        while deque and nums[deque[-1]] < nums[i]:
            deque.pop()
        
        # 将当前元素加入队列尾部
        deque.append(i)
        
        # 记录窗口中的最大值