滑動窗口

最大子數組和

題目描述

給你一個整數數組 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^5
• 1 <= nums[i] <= 50
• 1 <= 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<=1000
• 1<=b<=m<=1000
• 1<=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++;  //在自增之前判斷是否為0while(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或1void makeBalance() {if (smallSize > largeSize + 1) {// small 比 large 元素多 2 個large.push(small.top());small.pop();--smallSize;++largeSize;// small 堆頂元素被移除，堆頂元素變化，需要進行 pruneprune(small);}else if (smallSize < largeSize) {// large 比 small 元素多 1 個small.push(large.top());large.pop();++smallSize;--largeSize;// large 堆頂元素被移除，堆頂元素變化，需要進行 pruneprune(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;}
};