【每日一题】滑动窗口题解

常规做法当然是单调队列，但我全都要。

单调队列

Solution

求最大值和最小值的方法实际上是一样的。

这里只以求最大值为例：

从左往右扫到某一个值的时候，如果当前值的大小比前面的某些值要大的时候，结尾是当前位置往右的的最大值就不可能是前面比当前值小的。

还有一种情况是队头已经超出这个区间范围了，这个时候就需要先把他给剔除。

于是构造一个单调队列，队头是值较大的一端，而队尾是值较小的一端，那么构造好每一个位置的单调队列后，单调队列的队头就是这个区间的最大值。

时间复杂度 空间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
vector<int> calc(vector<int> a, int k, bool isMin) {
  const int n = a.size();
  // 如果是求最小值，取负数做一遍求最大值的，然后再将结果取负数即可
  if(isMin) for(int &x: a) x = -x;
  deque<int> q; // 双端队列
  vector<int> ret(n - k + 1); // 返回的数组
  for(int i = 0; i < n; i++) {
    while(!q.empty() && q.front() <= i - k) q.pop_front(); // 下标超出区间
    // 构造出单调队列 将没有机会成为最大值的出队
    while(!q.empty() && a[q.back()] < a[i]) q.pop_back();
    q.push_back(i);
    // 队头作为最大值
    if(i + 1 >= k) ret[i + 1 - k] = a[q.front()];
  }
  if(isMin) for(int &x: ret) x = -x;
  return ret;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for(int &x: a) cin >> x;
  vector<int> res = calc(a, k, true); // 计算各区间最小值
  for(int i = 0; i < n - k + 1; i++) {
    cout << res[i] << " \n"[i == n - k];
  }
  res = calc(a, k, false); // 计算各区间最大值
  for(int i = 0; i < n - k + 1; i++) {
    cout << res[i] << " \n"[i == n - k];
  }
}

ST表

Solution

ST表可以预处理数组，然后可以询问每一个区间内的最大值或者是最小值。

那么就可以很轻松地MLE这一道题了。

怎么卡我内存啊！！算了一下发现确实不行。

下面代码只过了50%。

时间复杂度 空间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
// 建ST表
template<typename T>
struct ST {
  vector<vector<pair<T, T>>> dp;
  vector<int> lg;
  // 预处理 O(nlog(n))
  ST(const vector<T> &a) {
    const int n = a.size(), m = 33 - __builtin_clz(n);
    // 申请足够的空间 需要的空间有点多
    dp = vector<vector<pair<T, T>>>(n + 1, vector<pair<T, T>>(m));
    lg = vector<int> (n + 1, 0);
    for(int i = 1; i <= n; i++) {
      dp[i][0] = {a[i - 1], a[i - 1]}, lg[i] = lg[i >> 1] + 1;
    }
    for(int j = 1; (1 << j) <= n; j++) {
      for(int i = 1; i + (1 << j) - 1 <= n; i++) {
        pair<T, T> &x = dp[i][j - 1], &y = dp[i + (1 << (j - 1))][j - 1];
        dp[i][j] = {min(x.first, y.first), max(x.second, y.second)};
      }
    }
  }
  // 询问 O(1)
  pair<T, T> minmax(int l, int r) {
    l++, r++;
    int k = lg[r - l + 1] - 1;
    return {
      min(dp[l][k].first, dp[r - (1 << k) + 1][k].first), 
      max(dp[l][k].second, dp[r - (1 << k) + 1][k].second)
    };
  }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, k; cin >> n >> k;
  vector<int> v(n);
  for(int &x: v) cin >> x;
  ST<int> obj(v);
  vector<int> a1(n - k + 1), a2(n - k + 1);
  for(int i = k - 1; i < n; i++) {
    tie(a1[i - k + 1], a2[i - k + 1]) = obj.minmax(i - k + 1, i);
  }
  for(int i = 0; i < n - k + 1; i++) {
    cout << a1[i] << " \n"[i == n - k];
  }
  for(int i = 0; i < n - k + 1; i++) {
    cout << a2[i] << " \n"[i == n - k];
  }
}

线段树

Solution

线段树就很强大了，相比于ST表还可以支持修改内存也只是，但是各种操作的复杂度都是的而不是的。

建完线段树暴力就完事了。

可恶啊，最小值和最大值一起求还是会MLE。那只能分开来求，而且分开来求的话就不需要把答案存起来。

时间差点超了但是能过就行嘻嘻。

时间复杂度 空间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
#define lson i << 1, l, mid
#define rson i << 1 | 1, mid + 1, r
#define mid ((l + r) >> 1)
const int N = 1000000 + 10;
int b[N << 2], a[N];
// 线段树建树
void build(int i, int l, int r, bool is) {
  if(l == r) { b[i] = a[l]; return; }
  build(lson, is); build(rson, is);
  if(is) b[i] = min(b[i << 1], b[i << 1 | 1]);
  else b[i] = max(b[i << 1], b[i << 1 | 1]);
}
// 线段树查询
int query(int i, int l, int r, int L, int R, bool is) {
  // 超出范围返回一个极限值
  if(r < L || l > R) return is ? INT_MAX : INT_MIN;
  if(L <= l && r <= R) return b[i];
  if(is) return min(query(lson, L, R, is), query(rson, L, R, is));
  else return max(query(lson, L, R, is), query(rson, L, R, is));
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, k; cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i];
  build(1, 1, n, true);
  for(int i = k; i <= n; i++) {
    cout << query(1, 1, n, i - k + 1, i, true) << " \n"[i == n];
  }
  build(1, 1, n, false); // 省点空间做build两次线段树
  for(int i = k; i <= n; i++) {
    cout << query(1, 1, n, i - k + 1, i, false) << " \n"[i == n];
  }
}