滑动窗口
最大子数组和
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
思路分析
见代码注解
代码
int maxSubArray(vector<int>& nums) {
int numsSize=nums.size();
int max=nums[0];
int m=0;
for(int i=1;i<numsSize;i++)
{
m+=nums[i-1]; //m记录前面区间窗口区间的总和
if(m<0)
{
m=0; //当区间总和小于0时放弃不用，m置为0
}
if(m+nums[i]>max)
{
max=m+nums[i]; //更新max值。
}
}
return max; //如果数组值都为非正数，则最大值为某个元素
}
子数组操作后的最大频数
问题描述
给你一个长度为 n 的数组 nums ，同时给你一个整数 k 。
你可以对 nums 执行以下操作 一次 ：
- 选择一个子数组
nums[i..j]，其中0 <= i <= j <= n - 1。 - 选择一个整数
x并将nums[i..j]中 所有 元素都增加x。
请你返回执行以上操作以后数组中 k 的 最大 频数。
子数组 是一个数组中一段连续 非空 的元素序列。
提示：
1 <= n == nums.length <= 10^51 <= nums[i] <= 501 <= k <= 50
思路分析
记数组中k的频数为cnt，可以肯定答案最小不会小于cnt(将数组中所有元素加0得到)
将子数组中所有元素都加x，为最大化答案，最优策略就是将子数组中频数最大的那个元素变为k（如果使对答案贡献为负数，那就不能操作该子数组）。
定义m_max[i]记录将元素i全变为k对答案的贡献，maxn为所有m_max[i]的最大值，最后的答案就是cnt+maxn。
具体实现时，再定义一个数组m，m[i]记录将最后枚举到的i的下标为操作的子数组的右边界且将i都变为k的对答案的最大贡献，枚举到nums[i]，当nums[i]==k时，将前面统计到的所有的大于0的m[j]都减1，因为后面再枚举到j时，前面有一个k，对答案的贡献要减1，贡献本身就是0了就没必要再减了。
本题思路和上题最大子数组和的思路有点像。m[i]记录的是前缀和(遇到i加一，遇到k减1)，m_max[i]记录的是i对应的最大子数组和。
代码
int maxFrequency(vector<int>& nums, int k) {
int ans=0,cnt=0,n=nums.size();
vector<int>m(51);
vector<int>m_max(51); //m_max[i]记录将元素i全变为k对答案的贡献
int maxn=0;
for(int i=0;i<n;i++){
int t=nums[i];
if(t==k){
cnt++; //记录k的个数
for(int j=1;j<=50;j++) if(m[j]>0) m[j]--;
}
else m[t]++;
m_max[t]=max(m[t],m_max[t]);
maxn=max(maxn,m_max[t]);
}
return cnt+maxn;
}
滑动窗口最大值
问题描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 数组，数组每个元素记录了滑动窗口每个阶段的最大值。
思路分析
这题是滑动窗口的经典题。
定义一个单调队列（双端队列实现），队头维护的是窗口的最大值，每次滑动将当前枚举到的新元素nums[i]尾插入队列，在插入前将影响单调的元素从尾部移除。
细节：当从队头取出元素时，有些元素可能已过期（不满足当前窗口大小为k），需要从头部移除,因为需要判断元素是否过期，这知道元素的下标，所以单调队列应该存储下标值。
代码
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> arr;
deque<int>q;
for(int i=0;i<nums.size();i++)
{
while(!q.empty()&&nums[q.back()]<nums[i]) q.pop_back();
q.push_back(i);
if(i>=k-1)
{
while(q.front()<=i-k) q.pop_front();
arr.push_back(nums[q.front()]);
}
}
return arr;
}
子矩阵
蓝桥杯2023年省赛题
问题描述
给定一个n*m的矩阵。设矩阵的价值为所有数中最大值与最小值的乘积。求给定的所有大小为a*b的子矩阵的价值的和。
答案很大，请输出答案对998244353的结果。
数据规模：
1<=a<=n<=10001<=b<=m<=10001<=aij<=1^9
思路分析
本题是滑动窗口最值的二维版本，请先回顾上题。
首先考虑暴力法，枚举每个子矩阵，总复杂度接近O(n*m*a*b),是个天文数字，肯定不允许。从数据规模来看需要设计一个O(n*m)的算法。
类似求一维的固定长度的子数组的最值，本题是求二维的固定长宽的子矩阵的最值。
参考滑动窗口最大值，先预处理数据，将原矩阵的每一行看作一维数组，对每一行求滑窗最值，定义maxn[i][j]表示第i行第j个长度为b的滑动窗口的最大值，同理定义minn[i][j]表示第i行第j个长度为b的滑动窗口的最小值。
再在maxn和minn的基础上求滑动窗口的最大值和最小值，滑动窗口的大小为a，这样通过横向再纵向扫描的方式求解。
以求2*3子矩阵最大值为例，图解：
代码中多次求解滑窗最值，可以定义getMin()和getMax()来快速求解。
时间复杂度：单次求解滑窗最值是线性的时间复杂度，求解minn,maxn的复杂度为O(n*m)，再在minn和maxn基础上求解滑窗最值的时间复杂度为O(n*c)(c为minn和maxn的列宽即m-b)，总时间复杂度为O(n*m+n*c)比O(n*m*a*b)好多了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a, b;
const int mod = 998244353;
vector<vector<int>>nums; //存储原数组
vector<vector<int>>maxn; //maxn[i][j]存储第i行第j个滑动窗口的最大值
vector<vector<int>>minn; //maxn[i][j]存储第i行第j个滑动窗口的最小值
void getMin(vector<int>& tar, vector<int>& mats, int k) { //求解滑动窗口最小值的子问题
deque<int>dq;
for (int i = 0; i < mats.size(); i++) {
while (!dq.empty() && mats[dq.back()] > mats[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) {
while (dq.front() <= i - k) dq.pop_front();
tar.push_back(mats[dq.front()]);
}
}
}
void getMax(vector<int>& tar, vector<int>&mats, int k) { //求解滑动窗口最大值的子问题
deque<int>dq;
for (int i = 0; i < mats.size(); i++) {
while (!dq.empty() && mats[dq.back()] < mats[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) {
while (dq.front() <= i - k) dq.pop_front();
tar.push_back(mats[dq.front()]);
}
}
}
void init() {
cin >> n >> m >> a >> b;
nums = vector<vector<int>>(n, vector<int>(m));
minn.resize(n);
maxn.resize(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> nums[i][j];
}
}
}
int solve() {
ll ans = 0;
for (int i = 0; i < n; i++) getMax(maxn[i], nums[i], b);
for (int i = 0; i < n; i++) getMin(minn[i], nums[i], b);
int cols = maxn[0].size();
vector<int>sMax, sMin; //子矩阵的最大最小值
vector<int>temp(n);
for (int j = 0; j < cols; j++) {
for (int i = 0; i < n; i++) temp[i] = maxn[i][j];
sMax.clear(); //容器清空，达到复用的目的，节省空间
getMax(sMax, temp, a);
for (int i = 0; i < n; i++) temp[i] = minn[i][j]; //同上
sMin.clear();
getMin(sMin, temp, a);
for (int i = 0; i < sMin.size(); i++) {
ans = (ans + ((ll)sMax[i] * sMin[i]) % mod) % mod;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
init();
cout << solve();
return 0;
}
最小区间
问题描述
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
思路分析
首先将列表中元素（额外记录所在区间）装进一个集合count中并按升序排好序，定义一个左边界left，右边界right，先正向遍历右边界，直到所有列表中的元素都至少出现一次，然后正向遍历左边界直到存在一个列表的元素没出现，将当前满足要求的区间[nums[left],nums[right]]与历史最优值比较并更新历史最优值。
从小到大遍历右边界寻找最大的左边界，确保计算了每个可能更新历史最值的答案。
代码
vector<int> smallestRange(vector<vector<int>>& nums) {
vector<pair<int, int>> count;
int k = nums.size();
for(int i = 0; i < k; ++i){
for(auto num : nums[i])
count.push_back({num, i});
}
sort(count.begin(), count.end()); //基本有序的排序，时间复杂度为O（nk）
int ans_left = 0, ans_right = INT_MAX; //历史最优值
vector<int> map(k); //map[i]统计第i个列表在当前区间出现了多少次
int kinds = 0; //统计有多少个列表的至少一个元素出现
for(int left = 0, right = 0; right < count.size(); ++right){
if(!map[count[right].second]++) kinds++; //在自增之前判断是否为0
while(kinds == k){
if(count[right].first - count[left].first < ans_right - ans_left){ //更新历史最值
ans_right = count[right].first;
ans_left = count[left].first;
}
if(--map[count[left++].second] == 0) kinds--; //自减之后判断是否为0
}
}
return {ans_left, ans_right};
}
时间复杂度O(nk）
最小覆盖子串
问题描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
思路分析
首先考虑一下暴力一点的方法
定义l，r [l,r]表示当前遍历到的区间窗口
定义一个字符表table储存区间内的字符的频数，当区间中的t中的某字符的频数都达标时，在不破坏达标条件的前提下逐渐向右移动左边界l
此时的r-l+1是以r为右边界的最小达标子串，每遍历一次r更新历史最小长度值和起始左边界。
上述思路，每遍历到一个r就需要去table中挨个检查每个字符的频数是否达标，又要多一层循环，能不能优化一些呢？
我们可以先对table预处理，让t中的字符对应的频数的负数存进table，表示t中对应字符需要补充的数量
在后面正式右边界遍历时一共需要补充tLen（t字符串的长度）个目标字符。
每次只需在O(1)的时间复杂度下判断tLen是否等于0即可判断区间内目标字符频数是否达标。
右边界每遍历到一个字符，对应字符频数+1，
频数+1之前判断该字符对应的频数是否为负数（表示该字符需要补充），是负数则tLen-1表示已补充一个目标字符，
当tLen减为0时，表示目标字符全部补充完（即窗口区间中t对应的字符数都达标），此时便在不破坏达标条件的前提下逐渐向右移动左边界（对应的字符频数大于0则减1且右移l，）。
当tlen减为0时，由于移动左右边界都不破坏达标条件，table存储的每个字符频数始终大于等于0，tLen便一直为0了（待补充目标字符数为0）。
代码
int table[26]={0};
int start=-1;
int leng=INT_MAX;
string minWindow(string s, string t) {
for (int i = 0; i < t.length(); i++) { //存储字符表
table[t[i]-'A']--;
}
for (int l = 0, r = 0,debt=t.length(); r < s.length(); r++) { //枚举右边界
if ((table[s[r]-'A']++)< 0) debt--; //debt减到0后不会再减
if (debt == 0) {
while (table[s[l]-'A'] > 0) table[s[l++]-'A']--; //table[i]最减到0后不会再减
if (r - l + 1 < leng) {
leng = r - l + 1; //更新最小长度
start = l; //更新起始索引
}
}
}
return start == -1 ? "" : s.substr(start, leng);
}
数据流的中位数
问题描述
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
思路分析
定义一个升序的优先队列（大根堆）queMin，队列中的所有元素都小于等于当前集合的中位数。
定义一个降序序的优先队列（小根堆）queMax，队列中的所有元素都大于当前集合的中位数。
每往集合添加一个数x
- 若x小于等于queMin堆顶或queMin为空，则将x添加进queMin，添加完后，判断queMin的大小大于queMax的大小+1（此时小于等于中位数的个数过多），则将queMin的堆顶元素移动到queMax
- 否则，将x添加进queMax，添加完后，判断queMax的大小大于queMin的大小（此时大于中位数的个数过多），则将queMax的堆顶元素移动到queMin
返回当前集合的中位数，若queMin的大小大于queMax，则返回queMin的堆顶元素，否则返回queMin堆顶元素和queMax堆顶元素的平均值。
代码
class MedianFinder {
public:
priority_queue<int>queMin; //升序，队头为最大值
priority_queue<int,vector<int>,greater<int>>queMax; //降序，队头为最小值
MedianFinder() {
}
void addNum(int num) {
if (queMin.empty() || num <= queMin.top()) {
queMin.push(num);
if (queMax.size() + 1 < queMin.size()) {
queMax.push(queMin.top()); //将小于等于中位数队列中的最大值移动到大于中位数队列
queMin.pop();
}
} else {
queMax.push(num);
if (queMax.size() > queMin.size()) {
queMin.push(queMax.top()); //将大于中位数队列中的最小值移动到小于等于中位数队列
queMax.pop();
}
}
}
double findMedian() {
if(queMin.size()>queMax.size()) return queMin.top();
return ((double)queMin.top()+(double)queMax.top())/2;
}
};
滑动窗口中位数
问题描述
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是3[2,3]，中位数是(2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
原题链接
思路分析
我们首先思考一下完成本题需要做哪些事情：
初始时，我们需要将数组 nums 中的前 k 个元素放入一个滑动窗口，并且求出它们的中位数；
随后滑动窗口会向右进行移动。每一次移动后，会将一个新的元素放入滑动窗口，并且将一个旧的元素移出滑动窗口，最后再求出它们的中位数。
因此，我们需要设计一个「数据结构」，用来维护滑动窗口，并且需要提供如下的三个接口：
insert(num)：将一个数 num 加入数据结构；
erase(num)：将一个数 num 移出数据结构；
getMedian()：返回当前数据结构中所有数的中位数。
使用两个优先队列（堆）维护所有的元素，第一个优先队列 small 是一个大根堆，它负责维护所有元素中较小的那一半；第二个优先队列 large 是一个小根堆，它负责维护所有元素中较大的那一半。（参考上一题）
延迟删除
对于insert添加元素来说比较简单，然而对于 erase(num) 而言，设计起来就不是那么容易了，因为我们知道，优先队列是不支持移出非堆顶元素这一操作的，因此我们可以考虑使用「延迟删除」的技巧
当我们需要移出优先队列中的某个元素时，我们只将这个删除操作「记录」下来，而不去真的删除这个元素。当这个元素出现在 small 或者 large 的堆顶时，我们再去将其移出对应的优先队列。
「延迟删除」使用到的辅助数据结构一般为哈希表 delayed，其中的每个键值对 (num,freq)，表示元素 num 还需要被删除 freq 次。
我们首先设计一个辅助函数 prune(heap)，它的作用很简单，就是对 heap 这个优先队列（small 或者 large 之一），不断地弹出其需要被删除的堆顶元素，并且减少 delayed 中对应项的值。在 prune(heap) 完成之后，我们就可以保证 heap 的堆顶元素是不需要被「延迟删除」的。
在 prune(heap) 的基础上设计另一个辅助函数 makeBalance()，它的作用即为调整 small 和 large 中的元素个数，使得二者的元素个数满足要求，即small.size()-large.size()的值为0或1。调整策略如下：
如果 small 和 large 中的元素个数满足要求，则不进行任何操作；
如果 small 比 large 的元素个数多了 2 个，那么我们我们将 small 的堆顶元素放入 large。此时 small 的对应元素可能是需要删除的，因此我们调用 prune(small)；
如果 small 比 large 的元素个数少了 1 个，那么我们将 large 的堆顶元素放入 small。此时 large 的对应的元素可能是需要删除的，因此我们调用 prune(large)。
此时，我们在原先 insert(num) 的设计的最后加上一步 makeBalance() 调整两个优先队列大小即可。
对于erase(num)还需进一步思考:
如果 num 与 small 和 large 的堆顶元素都不相同，那么 num 是需要被「延迟删除」的，我们将其在哈希表中的值增加 1；
否则，例如 num 与 small 的堆顶元素相同，那么该元素是可以理解被删除的。虽然我们没有实现「立即删除」这个辅助函数，但只要我们将 num 在哈希表中的值增加 1，并且调用「延迟删除」的辅助函数 prune(small)，那么就相当于实现了「立即删除」的功能。
无论是「立即删除」还是「延迟删除」，其中一个优先队列中的元素个数（这里指的是当前包含的个数，实际大小扣除延迟删除的个数）都发生了变化（减少了 1），因此我们还需要用 makeBalance() 调整元素的个数。
此时，所有的接口都已经设计完成了。由于 insert(num) 和 erase(num) 的最后一步都是 makeBalance()，而 makeBalance() 的最后一步是 prune(heap)，因此我们就保证了任意操作完成之后，small 和 large 的堆顶元素都是不需要被「延迟删除」的，且两个堆的元素个数符合要求。
具体实现的细节相对较多，读者可以参考下面的代码和注释进一步理解。
代码
class DualHeap {
private:
// 大根堆，维护较小的一半元素
priority_queue<int> small;
// 小根堆，维护较大的一半元素
priority_queue<int, vector<int>, greater<int>> large;
// 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
unordered_map<int, int> delayed;
int k;
// small 和 large 当前包含的元素个数，扣除被「延迟删除」的元素
int smallSize, largeSize;
public:
DualHeap(int _k): k(_k), smallSize(0), largeSize(0) {}
private:
// 不断地弹出 heap 的堆顶元素，并且更新哈希表
template<typename T> //标记为模版函数
void prune(T& heap) {
while (!heap.empty()) {
int num = heap.top();
if (delayed.count(num)) {
--delayed[num];
if (!delayed[num]) { //延迟删除数减为0，不需要再删除
delayed.erase(num);
}
heap.pop();
}
else {
break;
}
}
}
// 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
//即 small.size()-large.size()的值为0或1
void makeBalance() {
if (smallSize > largeSize + 1) {
// small 比 large 元素多 2 个
large.push(small.top());
small.pop();
--smallSize;
++largeSize;
// small 堆顶元素被移除，堆顶元素变化，需要进行 prune
prune(small);
}
else if (smallSize < largeSize) {
// large 比 small 元素多 1 个
small.push(large.top());
large.pop();
++smallSize;
--largeSize;
// large 堆顶元素被移除，堆顶元素变化，需要进行 prune
prune(large);
}
}
public:
void insert(int num) {
if (small.empty() || num <= small.top()) {
small.push(num);
++smallSize;
}
else {
large.push(num);
++largeSize;
}
makeBalance();
}
void erase(int num) {
++delayed[num];
if (num <= small.top()) {
--smallSize;
if (num == small.top()) {
prune(small);
}
}
else {
--largeSize;
if (num == large.top()) {
prune(large);
}
}
makeBalance();
}
double getMedian() {
return k & 1 ? small.top() : ((double)small.top() + large.top()) / 2;
}
};
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
DualHeap dh(k);
for (int i = 0; i < k; ++i) {
dh.insert(nums[i]);
}
vector<double> ans = {dh.getMedian()};
for (int i = k; i < nums.size(); ++i) {
dh.insert(nums[i]);
dh.erase(nums[i - k]);
ans.push_back(dh.getMedian());
}
return ans;
}
};