滑動窗口(尺取法

• 1. 介紹
• 2. 滑動窗口法的大體框架
• 4、最小覆蓋子串
• 5、窗口數量
• 6、最小值

1. 介紹

滑動窗口法，也叫尺取法（可能也不一定相等，大概就是這樣 =。=），可以用來解決一些查找滿足一定條件的連續區間的性質（長度等）的問題。由于區間連續，因此當區間發生變化時，可以通過舊有的計算結果對搜索空間進行剪枝，這樣便減少了重復計算，降低了時間復雜度。往往類似于“請找到滿足xx的最x的區間（子串、子數組）的xx”這類問題都可以使用該方法進行解決。

2. 滑動窗口法的大體框架

滑動窗口算法的思路是這樣：
1、我們在字符串 S 中使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引閉區間 [left, right] 稱為一個「窗口」。
2、我們先不斷地增加 right 指針擴大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此時，我們停止增加 right，轉而不斷增加 left 指針縮小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同時，每次增加 left，我們都要更新一輪結果。
4、重復第 2 和第 3 步，直到 right 到達字符串 S 的盡頭。
這個思路其實也不難，第 2 步相當于在尋找一個「可行解」，然后第 3 步在優化這個「可行解」，最終找到最優解。左右指針輪流前進，窗口大小增增減減，窗口不斷向右滑動。

3、長度最小的子數組
題意:給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組。如果不存在符合條件的連續子數組，返回 0。

解題思路：我們設置一個狀態為summation，表示當前區間的和，而狀態滿足的條件是summation >= s，尋找最優值則是去比較當前的最優值以及目前滑動窗口的長度。代入框架即得到了求解該問題的程序：

int main() {cin >> n >> s;for (int i = 0 ; i < n ; ++i)cin >> a[i];int left = 0, right = 0, res = INF;int sum = 0;while (right < n) {sum += a[right];while (sum >= s) {res = min(res, right - left + 1);sum -= a[left++];}right++;}

4、最小覆蓋子串

題意：給定大小為 N 的數組 a1?,a2?,a3?,…,aN? 和一個整數 S, 找到最小的子數組的大小(最小的窗口長度)滿足子數組包含區間 [1,S] 內的所有整數.不存在則輸出 0.

while (right < n ) {//只記錄我們需要的if (t.count(a[right]) ) {w[a[right]]++;//只在等于的時候加1，那么這個的數量如果等于m的話，就說明當前窗口內是覆蓋了的，而不是大于等于if (w[a[right]] == t[a[right]])cnt++;}right++;while (cnt == m) {res = min(res, right - left);int tp = a[left++];//當時記錄中的才減if (t.count(tp)) {w[tp]--;if (w[tp] < t[tp])cnt--;}}}

5、窗口數量

題目大意：給定大小為 N 的數組 a1?,a2?,a3?,…,aN? 和 Q 個整數 xi? 表示查詢, 對于每次查詢輸出滿足 1≤l≤r≤N 并且 al?+al+1?+…+ar?1?+ar?≤xi? 的區間 (l,r) 的數量.

解題思路：我們最主要的問題是在維護這個窗口的時候如何，統計個數，假設我們有一個區間[l,r]滿足條件，原本的所以可能區間數量應該有c(n,2)個，但是如果我們往右移動的時候，就有可能會出現重復計算的個能，這個重復計算是在原本窗口內的數導致的，利用這個特點我們每一次都用最新進入的滿足條件的來與在窗口內部在左邊的組合（r-l+1）。

6、最小值

對于數據范圍小的可以利用單調隊列來求，這是我們真的體會到了，為什么要在數組存的是小標了，是因為我們存下標才能維護這個窗口真實的一個大小，有因為隊列的第一個元素對應的小標是最小值，因此但循環到第i個的時候，if i - L + 1 > q[hh]就要去掉對首元素了，要加1，因為當到第i個元素的時候，是把第i個加進來的窗口最小值。

int main() {cin >> n >> L;for (int i = 0 ; i < n; ++i)cin >> a[i];int hh = 0, tt = -1;for (int i = 0 ; i < n ; ++i) {while (hh <= tt && i - L + 1 > q[hh])hh++;while (hh <= tt && a[i] <= a[q[tt]])tt--;q[++tt] = i;if (i >= L - 1)cout << a[q[hh]] << endl;}return 0; }

對于數據范圍大的話，可以利用線段樹求區間最小值。

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的算法篇之-----滑动窗口(尺取法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。