題目描述

有一個長為 ( n ) 的序列 ( a )，以及一個大小為 ( k ) 的窗口。現在這個窗口從左邊開始向右滑動，每次滑動一個單位，求出每次滑動后窗口中的最大值和最小值。例如：

數組是 ([1, 3, -1, -3, 5, 3, 6, 7])， ( k = 3 )。

輸入格式

輸入一共有兩行：

第一行有兩個正整數 ( n ) 和 ( k )。

第二行有 ( n ) 個整數，表示序列 ( a )。

輸出格式

輸出共兩行：

第一行為每次窗口滑動的最小值。

第二行為每次窗口滑動的最大值。

樣例

輸入數據 1

8 3
1 3 -1 -3 5 3 6 7

輸出數據 1

-1 -3 -3 -3 3 3
3 3 5 5 6 7

提示

數據范圍:

• 對于 50% 的數據，( 1 \leq n \leq 10^5 )
• 對于 100% 的數據，( 1 \leq k \leq n \leq 10^6 )，( a_i \in [-2^{31}, 2^{31}) )

參考代碼：雙端隊列實現

#include <bits/stdc++.h>using namespace std;constexpr int N = 1e6 + 7;int a[N], n, k;int main() {cin >> n >> k;for (int i = 0; i < n; i++) cin >> a[i];// 存的是下標// 我們的dq里面一定是單調// 你要么活得比我長// 要么能力比我強deque<int> dq;for (int i = 0; i < n; i++) {// 當前隊首的這個點還存活不 --- 窗口長度k// 比如我當前位置是i,窗口長度是3// 可以存在的點是i, i - 1, i - 2if (!dq.empty() && i - k + 1 > dq.front()) {// 比如我現在的i = 6，k = 3 --- 4 5 6三個位置的數// 但是你的dq.frond() = 3,你隊首是位置為3的元素// 已經過了你的時代 --- 你該下位了dq.pop_front();}// 我a[i]要把我前面能力沒我強,活的沒我久的全部干掉// 隊列里如果活得沒有a[i]久,能力沒有a[i]強,a[i]在的一天他們就永無出頭之日while (!dq.empty() && a[i] <= a[dq.back()]) dq.pop_back();dq.push_back(i);// 可以輸出當前的最小值了 --- 窗口長度至少得達到k才可以開始輸出if (i >= k - 1) cout << a[dq.front()] << " ";}cout << "\n";dq.clear();for (int i = 0; i < n; i++) {// 當前隊首的這個點還存活不 --- 窗口長度k// 比如我當前位置是i,窗口長度是3// 可以存在的點是i, i - 1, i - 2if (!dq.empty() && i - k + 1 > dq.front()) {// 比如我現在的i = 6，k = 3 --- 4 5 6三個位置的數// 但是你的dq.frond() = 3,你隊首是位置為3的元素// 已經過了你的時代 --- 你該下位了dq.pop_front();}// 我a[i]要把我前面能力沒我強,活的沒我久的全部干掉// 隊列里如果活得沒有a[i]久,能力沒有a[i]強,a[i]在的一天他們就永無出頭之日while (!dq.empty() && a[i] >= a[dq.back()]) dq.pop_back();dq.push_back(i);// 可以輸出當前的最小值了 --- 窗口長度至少得達到k才可以開始輸出if (i >= k - 1) cout << a[dq.front()] << " ";}cout << "\n";return 0;
}

參考代碼:手寫單調隊列

#include <bits/stdc++.h>using namespace std;constexpr int N = 1e6 + 7;int a[N], dq[N];int n, k, head = 0, tail = -1;bool isNotEmpty() { return head <= tail; }int top() { return dq[head]; }void pop_front() { head += 1; }int back() { return dq[tail]; }void pop_back() { tail -= 1; }void push(int x) { dq[++tail] = x; }int main() {cin >> n >> k;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < n; i++) {if (isNotEmpty() && i - k + 1 > top()) pop_front();while (isNotEmpty() && a[back()] >= a[i]) pop_back();push(i);if (i >= k - 1) cout << a[top()] << " ";}cout << "\n";head = 0, tail = -1;for (int i = 0; i < n; i++) {if (isNotEmpty() && i - k + 1 > top()) pop_front();while (isNotEmpty() && a[back()] <= a[i]) pop_back();push(i);if (i >= k - 1) cout << a[top()] << " ";}cout << "\n";return 0;
}