土豪

题目

世界上如果一定要有土豪，我希望他是我的朋友。

小J和小R今天在学计算机数学，现在老师让所有人都站成了一排，每个人现在都拥有了一个财富值。

小R："你说相邻的是不是都是我的朋友啊。"

小J："那我想找找谁是我最富有的朋友。"

小R："那你可以告诉我每几个人中谁最富有吗？"

小J："我……我努力……"

现在有 n 个人，站成了一排，请你找到他们中每 k 个人中所拥有的财富值最大是多少。

输入：第一行两个整数 n,k，n 表示总人数，k 表示在多少个人中找最大值。第二行 n 个整数，按顺序表示每个人的财富值。
输出：输出 n−k+1 个整数，依次表示每 k 个人中所拥有的最大财富值。

样例1：

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

3 3 5 5 6 7

样例2：

10 5
1 5 9 4 5 7 1 10 11 13

9 9 9 10 11 13

提示：对于 30% 的数据，保证 n≤100，k≤100。对于 60% 的数据，保证 n≤10000，k≤10000。对于 100% 的数据，保证 n≤1000000，k≤1000000，财富值都在 int 范围内。

思路

用单调递减队列维护滑动窗口的最大值。队列存下标，需要管理两个边界：队头下标若小于 i - k + 1，说明已滑出窗口，弹出；新元素入队前，将队尾所有比它小的元素弹出，保持队列单调递减。这样队头始终是当前窗口的最大值，每次 O(1) 取得。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,k; // 总人数，k个中找max
    cin>>n>>k;

    vector<int> wealth(n);
    for(int c=0;c<n;c++){
        cin>>wealth[c];
    }

    deque<int> dq;
    for(int i=0;i<n;i++){
        // 弹出窗口外的下标
        while(!dq.empty() && dq.front() <= i-k) dq.pop_front();
        // 弹出所有比当前元素小的元素
        while(!dq.empty() && wealth[dq.back()] < wealth[i]) dq.pop_back();
        dq.push_back(i);

        // 当窗口形成后，输出当前窗口的最大值（队首）
        if(i >= k-1){
            cout<<wealth[dq.front()];
            if(i!=n-1) cout<<' ';
        }
    }
    cout << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：O(n)，每个元素最多入队、出队各一次
• 空间复杂度：O(k)，队列最多存 k 个下标

← 返回菜鸟的coding