前言
寫下這篇文章的原因主要是本人在力扣86場雙周賽碰到的第四題，以為是dp，但其實是滑動視窗進行求解，以下特此記錄一下滑動視窗的幾種常見題型，也可以作為今后復習用的題單，
滑動視窗的本質
首先，得了解一下滑動視窗的本質，在我看來，滑動視窗本質是及時舍棄不需要的元素，
思路就是每次遍歷程序都要實作三部曲：
- 處理隊尾
- 處理隊頭
- 實時更新
題型1：單調佇列的模擬
239. 滑動視窗最大值
這道題基本上是這個題型我們做的第一題，主要原理就是手動實作一個雙端佇列，使得佇列里的數滿足嚴格單調遞增的規律，從而獲取在視窗內的最大最小值只需要O(1)的時間，具體代碼如下：
const int N = 1e5 + 10;
class Solution {
public:
int q[N], hh, tt = -1;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
for(int i = 0; i < nums.size(); ++ i) {
if(hh <= tt && i - k + 1 > q[hh]) hh ++;
while(hh <= tt && nums[q[tt]] <= nums[i]) tt --;
q[++ tt] = i;
if(i - k + 1 >= 0) res.push_back(nums[q[hh]]);
}
return res;
}
};
注意回圈內3、4行的順序不能交換，因為有可能新加入的這個數剛好是這個視窗內的最大值！
2398. 預算內的最多機器人數目
上題的拓展版本
const int N = 1e5;
class Solution {
public:
int q[N], hh = 0, tt = -1;
int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
int ans = 0;
long long s = 0;
int n = chargeTimes.size();
for(int l = 0, r = 0; r < n; ++r) {
// 處理隊尾
while(hh <= tt && chargeTimes[q[tt]] <= chargeTimes[r]) tt--;
q[++tt] = r;
s += runningCosts[r];
// 處理隊頭
while(hh <= tt && chargeTimes[q[hh]] + (r - l + 1) * s > budget) {
if(q[hh] == l) {
hh++;
}
s -= runningCosts[l];
++l;
}
// 實時更新
ans = max(ans, r - l + 1);
}
return ans;
}
};
題型2：字串匹配問題
這一類題型其實非常重要，我看了網上很多解法，看到一位叫做flix的大佬寫的非常好，他的模板可以秒殺非常多同類題目，強烈推薦！（見文末參考）
這類題型主要是通過滑動視窗和哈希表來解決！
題型2.1：變長滑動視窗
76. 最小覆寫子串
注意，其實這類題型的流程還是不離開上述所說的三部曲，下面貼一下flix大佬的思路詳解：
class Solution {
public:
string minWindow(string s, string t) {
string ans = "";
int ns = s.size(), nt = t.size();
if(ns < nt) return ans; // 特判
unordered_map<char, int> ht;
for(int i = 0; i < nt; ++i) ht[t[i]]++; // 統計所有t中字符個數
int need = nt; // 符合題意的視窗內必須含有的字符數量
int min_len = ns + 10; // 初始化為不可能達到的數
int st = -1;
for(int l = 0, r = 0; r < ns; ++r) { // 每次回圈右移r指標拓展視窗
if(ht.count(s[r])) { // 如果當前字符是t中出現的
if(ht[s[r]] > 0) need--; // 當前視窗內該字符數量還沒滿足的話，need--，說明又可以滿足一個
ht[s[r]]--; // 當前視窗仍舊需要該字符數量-1
}
while(need == 0) { // 滿足題意的視窗目標：need == 0
if(r - l + 1 < min_len) { // 更新最小字串
st = l;
min_len = min(min_len, r - l + 1);
ans = s.substr(st, min_len);
}
// 當前視窗已經滿足，開始右移l指標縮小視窗
if(ht.count(s[l])) { // 如果當前l指標指向的是t中出現的字符
if(ht[s[l]] == 0) need++; // 如果當前視窗只是剛好符合s[l]字符的數量要求，那么右移后勢必會不滿足，所需要的字符數need + 1
ht[s[l]]++; // 當前視窗仍舊需要該字符數量-1
}
l++; // 注意為什么l在這里+1，因為考慮到視窗記憶體在不是t中的字符，這樣在當前while回圈中可以不斷縮小視窗實作實時更新，比如t字符為ABC，當前視窗內為xxxBCA，這樣會不斷縮小，得到當前r指標情況下的最小的視窗，
}
}
return ans;
}
};
面試題 17.18. 最短超串
直接套模板
class Solution {
public:
vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
int nb = big.size(), ns = small.size();
unordered_map<int, int> cnt;
for (int i = 0; i < ns; ++i) cnt[small[i]]++;
int need = ns;
int min_len = nb + 1, st = -1, ed = -1;
for(int l = 0, r = 0; r < nb; ++r) {
if(cnt.count(big[r])) {
if(cnt[big[r]] > 0) need--;
cnt[big[r]]--;
}
while(need == 0) {
if(r - l + 1 < min_len) {
st = l, ed = r;
min_len = min(min_len, r - l + 1);
}
if(cnt.count(big[l])) {
if(cnt[big[l]] == 0) need++;
cnt[big[l]]++;
}
l++;
}
}
vector<int> ans;
if(~st && ~ed) {
ans.push_back(st);
ans.push_back(ed);
}
return ans;
}
};
題型2.2：定長滑動視窗
567. 字串的排列
在我看來，區別僅僅是左指標l的位置在每一步回圈中直接實時更新賦值即可
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size();
if(n1 > n2) return false;
unordered_map<char, int> cnt;
for (int i = 0; i < n1; ++i) cnt[s1[i]]++;
int need = n1;
for(int r = 0; r < n2; ++r) {
if(cnt.count(s2[r])) {
if(cnt[s2[r]] > 0) need--;
cnt[s2[r]]--;
}
int l = r - n1 + 1; // 注意這一步
if(l >= 0) { // 判斷定長的視窗是否形成
if(need == 0) return true;
if(cnt.count(s2[l])) {
if(cnt[s2[l]] >= 0) need++;
cnt[s2[l]]++;
}
}
}
return false;
}
};
題型3：滑動視窗+二分
220. 存在重復元素 III
還是走三部曲，外加用一個multiset存盤視窗內的元素，并在每次加入元素時二分查找set是否存在滿足題意的元素即可，
typedef long long ll;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n = nums.size();
multiset<ll> s;
for(int r = 0; r < n; ++r) {
ll lower = (ll)nums[r] - t, upper = (ll)nums[r] + t;
auto it = s.lower_bound(lower);
if(it != s.end() && *it <= upper) return true;
s.insert(nums[r]);
if(r - k >= 0) {find(nums[r - k]);
s.erase(it);
auto it = s.
}
}
return false;
}
};
參考
[1]『 一招吃遍七道 』滑動視窗的應用
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/504433.html
標籤：其他
上一篇：攻防世界 repeater 題解