題目描述

• 給定一個大小為n ≤ 10^6的數組。
• 有一個大小為k的滑動窗口，它從數組的最左邊移動到最右邊。
• 你只能在窗口中看到k個數字。
• 每次滑動窗口向右移動一個位置。以下是一個例子：
  • 該數組為 [1 3 -1 -3 5 3 6 7]，k為3。
    
• 你的任務是確定滑動窗口位于每個位置時，窗口中的最大值和最小值。

輸入格式

• 輸入包含兩行。
• 第一行包含兩個整數n和k，分別代表數組長度和滑動窗口的長度。
• 第二行有n個整數，代表數組的具體數值。同行數據之間用空格隔開。

輸出格式

• 輸出包含兩個。
• 第一行輸出，從左至右，每個位置滑動窗口中的最小值。
• 第二行輸出，從左至右，每個位置滑動窗口中的最大值。

基本思路

這道題是單調隊列系列題目的最基礎的模板題，但是對于像我這樣的初學者來說仍然難度較大，因此我將對該題的思路進行詳細解析。

• 算法題的核心是將一個有直觀、暴力的思路的算法優化為一個邏輯上更加復雜，但是時間和空間上更占優勢的算法。那么，對于這道題，我們就需要首先思考蠻力算法的求解步驟是什么。本題的蠻力算法非常直觀，就是一個簡單的雙重遍歷。例如，對于數組[1 3 -1 -3]，并假設窗口大小為3，那么我們就從數組的第一個元素開始遍歷，向右滑動窗口，每次遍歷到的數組元素作為窗口的左端點。以這個例子為例，可以得到兩個窗口[1 3 -1]和[3 -1 -3]，再分別從這兩個窗口中找出最大值和最小值即可。代碼實現上，可以大致如下：

#include <cstdio>
#include <vector>
using namespace std;// 本例子中n為4，k為3，假設原始數組為arr，本例子以最大值為例
for(int i = 0; i < n - k + 1; ++ i)
{// 使用一個向量表示當前窗口，并向該窗口中添加元素vector<int> window;for(int j = i; i < i + k; ++ j) window.push_back(arr[j]);// 查找該向量中的最大值并輸出int max = window[0];for(int j = 1; j < window.size(); ++ j) if(window[j] > max) max = window[j];printf("%d ", max);
}

• 但是，我們仔細考慮一下，這種方法存在明顯的冗余性。兩個相鄰的滑動窗口之間，有且只有一個元素不相同，而窗口中的其他元素都是完全一樣的，因此會經過多輪重復遍歷，創建多個大部分元素都相同的向量，算法的時間復雜度為O(nk)。既然存在冗余元素，那么我們就需要從數據結構和算法的角度上考慮對算法進行優化。
• 直觀上，我們可以發現既然相鄰的兩個窗口只有一個元素存在區別，即相當于下一個窗口的元素是去除了上一個窗口中的首元素，并且在后面添加了一個新元素，這就很類似于數據結構中常用的隊列數據結構。因此，如果能夠使用隊列來代替向量，那么就可以提高算法的效率。實現代碼如下：

#include <cstdio>
#include <deque>
using namespace std;// 首先創建一個隊列，并以第一個窗口中的元素進行初始化
deque<int> window;
for(int i = 0; i < k; ++ i) window.push_back(arr[i]);
// 每輪遍歷隊首元素出棧，并從隊尾入隊一個元素
for(int i = k; i < n - k + 1; ++ i)
{window.pop_front();window.push_back(arr[i]);// 查找當前隊列中的最大值int max = window.front();for(int item : window) if(item > max) max = item;printf("%d ", max);
}

• 基于隊列的實現代碼的確能夠有更高的時間效率，但是是否可以進一步優化呢？我們發現，盡管使用隊列可以更加方便地創建和維護一個窗口，而不像向量那樣需要每次完全重新新建一個，但是在查找最大值時，仍然需要遍歷整個隊列。如果我們想要繼續提高效率，就必須簡化查找過程，避免耗時的循環遍歷，此時就應該使用單調隊列進行處理。

• 仍然以[1 3 -1 -3]為例，當我們每一輪循環更新隊列時，我們可以修改我們的更新策略。下面進行舉例說明，以查找最大值為例。

  • 第一輪：隊列初始為空，因此直接將第一個元素1放入隊尾即可。
  • 第二輪：隊列目前為[1]，當前遍歷到的元素為3；由于3大于當前的隊尾元素1，因此如果3也放入隊尾后，在查找最大值的過程中，元素1一定不會成為任何一個窗口的最大值了。這是因為當元素1和元素3在同一個窗口中時，3比1大，因此最大值不可能是1；當元素1和元素3不在同一個窗口中時，只有一種可能，就是當前窗口中已經不包含1了，這是因為3在原始數組中排在1的后面，只要1在窗口中，3一定在窗口中，所以這種情況下，窗口中已經不包含有元素1，所以自然不會成為最大值。因此，可以認為隊列中的1為冗余元素，可以直接將其出隊。只有某個元素可能成為某個窗口的最大值時，才會被放入隊尾進入隊列中，而所有確定下來的冗余元素都出隊。所以，在第二輪迭代中首先通過上述比較過程，讓隊尾的1出隊，此時隊列為空，則直接把當前元素3放入隊列中。
  • 第三輪：隊列目前為[3]，當前遍歷到的元素是-1。由于隊尾元素3比-1更大，因此直接將-1入隊放入隊尾即可，這是因為3會在-1之前從隊頭離開隊列，此時-1就有可能成為某個窗口的最大值元素。
  • 第四輪：和第三輪類似，隊列目前是[3 -1]，當前遍歷到的元素是-3。由于隊尾元素-1比-3更大，因此直接將-3放入隊尾。

• 那么，應該如何確定何時要將隊頭元素出隊呢？隊頭元素出隊表示該元素已經不在當前的窗口中，最簡單的處理方法就是用另一個隊列記錄所有隊列中的元素在數組中的下標，并在每一輪的遍歷過程中，通過下標判定隊首元素是否在窗口中即可。下標隊列和元素隊列中的元素應該是一一對應的，需要同時添加和同時刪除。

實現代碼

#include <cstdio>
#include <deque>
using namespace std;const int N = 1e6 + 10;
int arr[N];int main(void)
{int n, k;scanf("%d%d", &n, &k);for(int i = 0; i < n; ++ i) scanf("%d", &arr[i]);deque<int> q;deque<int> index;// 最小值部分for(int i = 0; i < n; ++ i){while(!q.empty() && q.back() >= arr[i]){q.pop_back();index.pop_back();}q.push_back(arr[i]);index.push_back(i);if(i >= k && i - k == index.front()){q.pop_front();index.pop_front();}if(i > k - 2) printf("%d ", q.front());}// 清空兩個隊列，對稱地求解最大值q.clear();index.clear();printf("\n");for(int i = 0; i < n; ++ i){while(!q.empty() && q.back() <= arr[i]){q.pop_back();index.pop_back();}q.push_back(arr[i]);index.push_back(i);if(i >= k && i - k == index.front()){q.pop_front();index.pop_front();}if(i > k - 2) printf("%d ", q.front());}return 0;
}