连续固定区间最大值
- 涉及知识点:堆,栈、双指针、滑动窗口,双向队列、线段树,树状数组, dp 等。
题目
给你一个数组 nums
和一个大小为 k
的区间。这个区间可以从数组的最左侧不断移动到数组的最右侧。每个移动区间固定有 k
个数字。这个区间每次只向右移动一位。
让你返回移动过程中,这些固定区间中的最大值。
样例输入:
1
| nums = [1,3,-1,-3,5,3,6,7], k = 3
|
样例输出:
样例解释:
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(); } 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; }
|
该方案的时空复杂度分析如下:
这个是正确解,最优解,可给 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 分,通过。
该方案的时空复杂度分析如下:
其他思路参考
以下解法比较特殊,而且编码比较复杂,如果真的有候选人在面试中写了,可以考虑给 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; } 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; }
|
该方案的时空复杂度分析如下:
思路 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; 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) { 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; }
|
该方案的时空复杂度分析如下:
拓展
如果遇到水平比较高的候选人,比如具有 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)
内完成查询。
代码参考:
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; } }
|