單調(diào)隊(duì)列是一種主要用于解決滑動窗口類問題的數(shù)據(jù)結(jié)構(gòu)黎炉，即在長度為的序列中膜钓，求每個長度為
的區(qū)間的區(qū)間最值嗽交。他的時(shí)間復(fù)雜度為
。
單調(diào)隊(duì)列的基本思想是維護(hù)一個雙向隊(duì)列颂斜，遍歷序列夫壁，僅當(dāng)一個元素稱為某一個區(qū)間最值時(shí)保留它。
舉個例子沃疮，尋找窗口的最小值為：
| 數(shù)組 | 雙向隊(duì)列 | 說明 |
|---|---|---|
| 7 6 8 12 9 10 3 | 初始狀態(tài) | |
7 6 8 12 9 10 3 |
7 | 從 |
7 6 8 12 9 10 3 |
6 | 在 |
7 6 8 12 9 10 3 |
6 8 | 在 |
7 6 8 12 9 10 3 |
6 8 12 | 在 |
7 6 8 12 9 10 3 |
6 8 9 | 在 |
7 6 8 12 9 10 3 |
8 9 10 | 在 |
7 6 8 12 9 10 3
|
3 | 在 |
其的核心代碼為：
public class Template {
public void template(int[] nums, int m) {
int n = nums.length;
int[] ans = new int[n];
Deque<Integer> dq = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (!dq.isEmpty() && i - dq.peekFirst() >= m) dq.pollFirst();
while (!dq.isEmpty() && nums[dq.peekLast()] > nums[i]) dq.pollLast();
dq.addLast(i);
if (i >= m - 1) System.out.printf("%d ", nums[dq.peekFirst()]);
}
}
public static void main(String[] args) {
Template template = new Template();
template.template(new int[]{7, 6, 8, 12, 9, 10, 3}, 4);// 輸出 6 6 8 3
}
}
參考文獻(xiàn)：
