NC51001 Sliding Window 滑动窗口最大最小值问题 堆优化

经典问题,滑动窗口的最值问题,

• 堆优化

• 结构体保存数字的下标和数字本身

  struct Node {
    int id, val; //下标和值
    bool operator < (const Node& no) const {
        return val < no.val;
    }
    bool operator > (const Node& no) const {
        return val > no.val;
    }
  } ;

  • 用两个堆来模拟窗口(一个大根堆，一个小根堆)

    std::priority_queue<Node> q1; //大根堆
    std::priority_queue<Node, vector<Node>, greater<Node> > q2;

  • 初始化窗口内有个元素

    for(int i=1; i<m; i++) //初始化窗口里有m-1个元素
        q1.push({i, a[i]}), q2.push({i, a[i]});

• 每次加入一个元素,就把堆内不在窗口区间内的弹出

  for(int i=m; i<=n; i++) {
    q2.push({i, a[i]}); //每次加入一个元素
    while(tb.id <= i-m) q2.pop(); //并把所有下标小于窗口左端的值弹走
    printf("%d%c", tb.val, i==n?'\n':' '); //此时堆顶一定是最小值
  }

完整代码如下

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e6+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \
do { \
    cout << "\033[31;1m " << #x << " -> "; \
    err(x); \
} while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
    template <typename T>
    void read(T& x) {
        int f = 1; x = 0;
        char ch = getchar();

        while (ch < '0' || ch > '9') 
            { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') 
            { x = x * 10 + ch - '0'; ch = getchar(); }
        x *= f;
    }
};
using namespace FIO;
#endif

#define ta (q1.top())
#define tb (q2.top())

int n, m, Q, K, a[MAXN];
struct Node {
    int id, val;
    bool operator < (const Node& no) const {
        return val < no.val;
    }
    bool operator > (const Node& no) const {
        return val > no.val;
    }
} ;

std::priority_queue<Node> q1; //大根堆
std::priority_queue<Node, vector<Node>, greater<Node> > q2;

int main() {
#ifdef debug
    freopen("test", "r", stdin);
    clock_t stime = clock();
#endif
    read(n), read(m);
    for(int i=1; i<=n; i++) read(a[i]);
    for(int i=1; i<m; i++) //初始化窗口里有m-1个元素
        q1.push({i, a[i]}), q2.push({i, a[i]});

    for(int i=m; i<=n; i++) {
        q2.push({i, a[i]}); //每次加入一个元素
        while(tb.id <= i-m) q2.pop(); //并把所有下标小于窗口左端的值弹走
        printf("%d%c", tb.val, i==n?'\n':' '); //此时堆顶一定是最小值
    }
    for(int i=m; i<=n; i++) {
        q1.push({i, a[i]});
        while(ta.id <= i-m) q1.pop();
        printf("%d%c", ta.val, i==n?'\n':' ');
    }





#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
    return 0;
}