连续固定区间最大值

  • 涉及知识点：堆，栈、双指针、滑动窗口，双向队列、线段树，树状数组, dp 等。

题目

给你一个数组 nums 和一个大小为 k的区间。这个区间可以从数组的最左侧不断移动到数组的最右侧。每个移动区间固定有 k 个数字。这个区间每次只向右移动一位。

让你返回移动过程中，这些固定区间中的最大值。

样例输入：

1
nums = [1,3,-1,-3,5,3,6,7], k = 3

样例输出：

1
[3,3,5,5,6,7]

样例解释：

1
2
3
4
5
6
7
8
          移动情况              最大值
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

如果候选人询问到数据范围，可提示：

1
2
3
1 <= nums.size() <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.size()

思路描述

思路 1：暴力滑动 O(n^2)

暴力进行滑动窗口， 每次遍历当前窗口内的元素取最大值。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <vector>
#include <algorithm>
using namespace std;
vector<int> find_maximum_of_sgements(vector<int>&nums, int k) {
  vector<int> res;
  for (int i = 0; i + k <= nums.size(); i++) {
      res.push_back(*max_element(nums.begin() + i, nums.begin() + i + k));
  }
  return res;
}
int main() {
  return 0;
}

该方案的时空复杂度分析如下：

  • 时间复杂度 O(n * k)～O(n^2)
  • 空间复杂度 O(n - k + 1)

这个是暴力解，非正确解，只能给 2 分，可提示次优解和最优解

优化提示 1：可以优化到低于 O(n^2) 的吗？比如 O(nlogn)，O(nlogk), 甚至是线性 O(n) 的做法。

优化提示 2：可以想到用一些可以维护极值的数据结构做吗？

优化提示 3：那如果拆分成子问题，快速求连续区间的最大值，你怎么做才会有带 log 的时间复杂度？

提示后，候选人还是不会。可换题。

思路 2：堆 O(nlogk)

维护一个大小为 k 的堆，向堆中插入一个元素(单个操作时间复杂度 O(logk)), 将数据不断 push 进堆，每次取结果都将 top 的数取出来就是序列答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <queue>
#include <vector>
#include <utility>
vector<int> find_maximum_of_segments(vector<int>& nums, int k) {
  priority_queue< pair<int,int> > pq;
  vector<int> res;
  for(int i = 0;i < k;i++) {
      pq.push({nums[i],i});
  }
  res.push_back(pq.top().first);
  for(int i = k;i < nums.size(); i++) { 
      while(!pq.empty() && pq.top().second <= (i - k)) {
          pq.pop();
      }
      pq.push({nums[i],i});
      res.push_back(pq.top().first);   
  }
  return res; 
}
int main() {
  return 0;
}

该方案的时空复杂度分析如下：

  • 时间复杂度：O(nlogk), 候选人有可能写成O(nlogn), 但问题不大。
  • 空间复杂度：O(k)。

这个是正确解，但非最优解，可给 3 分，通过。

思路 3：双向队列 O(n)

可以维护一个双向队列，这个队列是递减的。队列用来保存可能是最大值的数字的 index。
当前窗口最大值的 index 在队首，当窗口滑动时，会进入一个新值，出去一个旧值，不断更新给出当前窗口的最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <vector>
#include <deque>
vector<int>find_maximum_of_segments(vector<int>&nums, int k) {
  deque<int> que;
  vector<int> res;
  int n = nums.size();
  for (int i = 0; i < n; i++){
      // 新元素入队时, 比队尾元素大的话则替代队尾元素
      while(!que.empty() && nums[i] > nums[que.back()]){
          que.pop_back();
      }
      // 检查队首的 index 是否在窗口内，不在则出队
      if(!que.empty() && que.front() < i - k + 1) {
          que.pop_front();
      }
      que.push_back(i);
      if (i >= k -1) {
        res.push_back(nums[que.front()]);
      }
  }
  return res;
}
int main() {
  return 0;
}

该方案的时空复杂度分析如下：

  • 时间复杂度：O(n)。
  • 空间复杂度：O(k)。

这个是正确解，最优解，可给 4 分，通过。

思路 4：dynamic programming

先将数组分割成有 k 个元素的块。
建立数组 left,其中 left[j] 是从块的开始到下标 j 最大的元素，方向： 左->右。
数组 right，其中 right[j] 是从块的结尾到下标 j 最大的元素，方向： 右->左。

从左到右遍历数组，建立数组 left。

从右到左遍历数组，建立数组 right。

因为一个窗口 [i, i + k - 1] 最多跨越两个块，所以求窗口中的最大值就是求这个窗口跨越的块中的最大值，
可以知道，无论是跨越 1 个块也好，2 个块也好，计算处于边界的 i 和 i + k - 1 对应的值即可。

right[i] 表示从块的结尾到下标 j 的最大的元素。

left[i + k - 1] 表示从块的开始到下标 i + k - 1 的最大的元素。

这两个范围刚好是整个窗口。

所以窗口的最大值是 max(right[i], left[i + k - 1])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <vector>
vector<int>find_maximum_of_segments(vector<int>&nums, int k) {
  vector<int> res;
  int n = nums.size();
  vector<int> left(n, 0), right(n, 0);
  int max_num;
  for(int i = 0; i < n; i ++){
      if(i % k == 0){
          max_num = nums[i];
      }
      max_num = max(max_num, nums[i]);
      left[i] = max_num;
  }
  max_num = nums[n - 1];
  for(int i = n - 1; i >= 0; i --){
      if(i % k == k - 1){
          max_num = nums[i];
      }
      max_num = max(max_num, nums[i]);
      right[i] = max_num;
  }
  for(int i = 0; i <= n - k; i ++){
      res.push_back(max(right[i], left[i + k - 1]));
  }
  return res;
}
int main() {
  return 0;
}

这个是正确解，最优解，但比较难想到。可给 5 分，通过。

该方案的时空复杂度分析如下：

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。

其他思路参考

以下解法比较特殊，而且编码比较复杂，如果真的有候选人在面试中写了，可以考虑给 5 分。

思路 4: 线段树 (segment tree)

比较裸的线段树维护极值的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
vector<int>tree;
void pushUp(int rt) {
  tree[rt] = max(tree[1 << rt], tree[1 << rt | 1]);
}

void build(int rt, int l,int r, vector<int>&nums) {
  if(l == r) {
    tree[rt] = nums[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(1 << rt, l, mid, nums);
  build(1 << rt | 1, mid + 1, r, nums);
  pushUp(rt);
}

int query(int rt, int l, int r, int ql, int qr) {
  if(l > r) {
    return INT_MIN;
  }
  if(l > qr || r < ql) {
    return INT_MIN;
  }
  // [ql [l, r] qr]
  if(l >= ql && r <= qr) {
      return tree[rt];
  }
  int mid = (l + r) >> 1;
  int left_val = query(1 << rt, l, mid, ql, qr);
  int right_val = query(1 << rt | 1, mid + 1, r, ql, qr);
  return max(left_val, right_val);
}

vector<int> find_maximum_of_segments(vector<int>& nums, int k) {
  int n = nums.size();
  vector<int> res;
  if(n == 0 || n < k) {
    return res;
  }
  tree.resize(1 << n);
  build(1, 0, nums.size() - 1, nums);
  for(int i = 0; i + k - 1 < n; i++) {
      int val = query(1, 0, n - 1, i, i + k - 1);
      res.push_back(val);
  }
  return res;
}
int main() {
  return 0; 
}

该方案的时空复杂度分析如下：

  • 时间复杂度：
    • 建树：O(n)。
    • 查询：O(logn)
  • 空间复杂度：O(3 * n)。

思路 5：树状数组 (fenwick tree)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int n;
vector<int>val;
vector<int>tmp;
const int MAX_VAL = 1e5;
int lowbit(int x){
  return x & -x;
}

void update(int x, int v){
  while(x <= n) {
    val[x] = v;
    // cout << "x = " << x << endl;
    int lx = lowbit(x);
    for(int i = 1; i < lx; i <<= 1) {
      val[x] = max(val[x], val[x - i]);
    }
    x += lowbit(x);
  }
}

int query(int l, int r){
  int ans = 0;
  while(r >= l) {
    // cout << "r = " << r << endl;
    ans = max(tmp[r - 1], ans);
    r--;
    while(r >= l + lowbit(r)){
        ans = max(val[r], ans);
        r -= lowbit(r);
    }
  }
  return ans;
}

vector<int> find_maximum_of_segments(vector<int>& nums, int k) {
  n = nums.size();
  vector<int> res;
  if(n == 0 || n < k) {
    return res;
  }
  val.resize(n + 1);
  for(int i = 0; i < n; i++) {
    int num = nums[i] + MAX_VAL;
    tmp.push_back(num);
    update(i + 1, num);
  }
  for(int i = 0; i + k - 1 < n; i++) {
    int max_val = query(i + 1, i + k);
    res.push_back(max_val - MAX_VAL);
  }
  return res;
}

int main() {
  return 0;
}

该方案的时空复杂度分析如下：

  • 时间复杂度：
    • 建树：O(n)。
    • 查询：O(logn)
  • 空间复杂度：O(3 * n)。

拓展

如果遇到水平比较高的候选人，比如具有 OI 或者 ACM 经历且实力比较强的候选人。

候选人只需要口述解法即可。

可将上面题目改编成：

题意不变，同样是给你一个数组 nums = [1,3,-1,-3,5,3,6,7] 和 一个 t, t 代表查询次数。
即存在多组查询，每次查询给你不一样的 k, 让你输出每个查询区间为 k 的区间的答案序列。

数据范围：

1
2
3
4
1 <= nums.size() <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.size()
1 <= t <= 10^3

样例输入

1
2
3
4
5
6
nums = [1,3,-1,-3,5,3,6,7], t = 5
k = 2
k = 3
k = 4
k = 5
k = 6

样例输出

1
2
3
4
5
3 3 -1 5 5 6 7
3 3 5 5 6 7 
3 5 5 6 7 
5 5 6 7 
5 6 7

思路 1

这种属于比较经典的 RMQ (Range Minimum/Maximum Query) 问题。

可以使用一种数据结构 Sparse Tables 来解决。

该数据结构可在 O(nlogn) 内完成数据预处理， 在 O(1) 内完成查询。

  • 时间复杂度：
    • 预处理：O(nlogn)。
    • 查询：O(1)
  • 空间复杂度：O(nlogn)。

代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int M;
void prepare(vector< vector<int> >&dp, vector<int>&nums) {
  for(int i = 0; i < nums.size(); i++) {
      dp[i][0] = nums[i];
  }
  for (int j = 1; j < M; j++) {
      for(int i = 0; i + (1 << j) - 1 <= nums.size(); i++) {
          dp[i][j] = max(dp[i][j-1], dp[i + (1 << (j - 1))][j-1]);
      }
  }
}
    
int query(vector< vector<int> >&dp, int l, int r) {
  int k = (int) (log(r - l + 1) / log(2));
  return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}

void find_maximum_of_segments(vector<int>&nums, int t) {
  int n = nums.size();
  M = (int) (log(n) / log(2)) + 1; 
  vector< vector<int> > dp(n + 1, vector<int>(M + 1, 0));
  prepare(dp, nums);
  int k;
  while(t--) {
    vector<int> res;
    cin >> k;
    for(int i = 0; i + k - 1 < nums.size(); i++) {
      res.push_back(query(dp, i, i + k - 1));
    }
    for(auto x: res) {
      cout << x << " ";
    }
    cout << endl;
  }
}