單調(diào)隊(duì)列所解決的問(wèn)題

單調(diào)隊(duì)列主要是為了求滑動(dòng)窗口最大/最小值。單調(diào)隊(duì)列是雙端隊(duì)列（首尾兩邊都可以append和pop）。具體而言，我們會(huì)在單調(diào)隊(duì)列的隊(duì)尾pop和append，會(huì)在隊(duì)首pop

滑動(dòng)窗口：只能左邊界L向右移動(dòng)或不動(dòng)、右邊界R向右移動(dòng)或不動(dòng)，二者不能向左移動(dòng)。

基本概念

單調(diào)隊(duì)列的類型：

從頭到尾遞減：可以求滑動(dòng)窗口內(nèi)的最大值
從頭到尾遞增：可以求滑動(dòng)窗口內(nèi)的最小值

我們之前學(xué)過(guò)單調(diào)棧：

由上圖可以看出，對(duì)于棧內(nèi)元素來(lái)說(shuō)：

• 在棧內(nèi)左邊的數(shù)就是數(shù)組中左邊第一個(gè)比自己小的元素；
• 但元素被彈出時(shí)，遇到的就是數(shù)組中右邊第一個(gè)比自己小的元素。

對(duì)于將要入棧的元素來(lái)說(shuō)：在對(duì)棧進(jìn)行更新后（即彈出了所有比自己大的元素），此時(shí)棧頂元素就是數(shù)組中左側(cè)第一個(gè)比自己小的元素；

由上圖可以看出，對(duì)于棧內(nèi)元素來(lái)說(shuō)：

• 在棧內(nèi)左邊的數(shù)就是數(shù)組中左邊第一個(gè)比自己大的元素；
• 但元素被彈出時(shí)，遇到的就是數(shù)組中右邊第一個(gè)比自己大的元素。

對(duì)于將要入棧的元素來(lái)說(shuō)：在對(duì)棧進(jìn)行更新后（即彈出了所有比自己小的元素），此時(shí)棧頂元素就是數(shù)組中左側(cè)第一個(gè)比自己大的元素；

！！！！！！！！！！！！！！單調(diào)隊(duì)列在這里的操作其實(shí)是和單調(diào)棧差不多的！！！！！！！！！！

為什么要選擇這樣的單調(diào)性：

首先規(guī)定隊(duì)首的元素是我們需要的最值（這一點(diǎn)非常重要），所以遞減隊(duì)列的隊(duì)首是最大值，遞增隊(duì)列的隊(duì)首是最小值。其次我們從下面對(duì)隊(duì)列中元素的理解也可以看到。從隊(duì)首到隊(duì)尾的元素成為所需最值的優(yōu)先級(jí)需要依次遞減。
在單調(diào)隊(duì)列中，頭和尾都可以pop，但只有尾可以append。

特別注意：單調(diào)隊(duì)列里存放的是index（下標(biāo)）而不是元素值（其實(shí)也可以是(value， index)這種），這是因?yàn)槲覀儫o(wú)法用元素值來(lái)判斷元素是否過(guò)期。但是我們?cè)谡務(wù)撛卮笮r(shí)，指的不是index的大小，而是index在原數(shù)組對(duì)應(yīng)value的大小。

用法

以求最大值的單調(diào)隊(duì)列為例，其進(jìn)出隊(duì)規(guī)則如下：

該單調(diào)隊(duì)列要求其中元素是從頭到尾遞減。遍歷一個(gè)數(shù)組，所有元素依次入隊(duì)。
在入隊(duì)時(shí)，若該元素比隊(duì)尾元素小，直接從隊(duì)尾入隊(duì)仍能保持單調(diào)性，那么從尾部直接入隊(duì)即可。
若該元素比隊(duì)尾元素大，那么要將隊(duì)尾元素不停pop，直到隊(duì)尾元素比該元素大（滿足單調(diào)性），將該元素從隊(duì)尾入隊(duì)。
另外注意，當(dāng)元素過(guò)期（已經(jīng)不在滑動(dòng)窗口內(nèi)），將該元素在隊(duì)首出隊(duì)。
什么時(shí)候生成記錄：每當(dāng)形成一個(gè)窗口時(shí)就收集答案。
如何獲取滑動(dòng)窗口的最大值：即雙端隊(duì)列頭部的值

理解單調(diào)隊(duì)列的進(jìn)出原因：

隊(duì)列中的元素表示，如果此時(shí)從左往右，那么從隊(duì)首到隊(duì)尾的元素表示能夠成為滑動(dòng)窗口最大值的優(yōu)先級(jí)（即哪些元素會(huì)依次稱為最大值）。優(yōu)先級(jí)高的元素應(yīng)當(dāng)值更大、值相同的情況下下標(biāo)更晚過(guò)期（這就處理了具有重復(fù)值的情況）。

我們按照這樣的理解來(lái)審視上面的進(jìn)出隊(duì)規(guī)則：

如果我們希望從隊(duì)尾入隊(duì)的元素比隊(duì)尾已有的元素大，說(shuō)明其稱為最大值的優(yōu)先級(jí)更高，所以需要pop掉已有的隊(duì)尾元素。如果希望入隊(duì)的元素比隊(duì)尾已有元素小，說(shuō)明其優(yōu)先級(jí)低，所以可以直接入隊(duì)。

對(duì)于重復(fù)值情況的說(shuō)明：當(dāng)即將入隊(duì)的元素和隊(duì)尾此時(shí)的元素重復(fù)的時(shí)候，新來(lái)的元素其下標(biāo)更晚過(guò)期，所以其優(yōu)先級(jí)更高，所以隊(duì)中的舊元素應(yīng)當(dāng)被pop掉。因此隊(duì)中的元素其實(shí)是嚴(yán)格遞減的。

如何解決滑動(dòng)窗口內(nèi)的最小值問(wèn)題呢？其實(shí)是一樣的，不過(guò)我們把最小值放在隊(duì)首，隊(duì)中元素依次遞增。

Java實(shí)現(xiàn)單調(diào)隊(duì)列

在Java中，我們可以通過(guò)繼承LinkedList類來(lái)實(shí)現(xiàn)一個(gè)單調(diào)隊(duì)列。下面是一個(gè)簡(jiǎn)單的單調(diào)遞增隊(duì)列的實(shí)現(xiàn)示例：

import java.util.LinkedList;public class MonotonicQueue {private LinkedList<Integer> queue;public MonotonicQueue() {queue = new LinkedList<>();}public void offer(int num) {// 維護(hù)單調(diào)性，移除所有比當(dāng)前元素大的元素while (!queue.isEmpty() && queue.getLast() < num) {queue.pollLast();}queue.offer(num);}public int peek() {return queue.peekFirst();}public int poll() {return queue.poll();}// 檢查隊(duì)列是否為空public boolean isEmpty() {return queue.isEmpty();}
}

單調(diào)隊(duì)列的c語(yǔ)言（數(shù)組版）

int deque[1000];
int h = 0, t = 0;
int pop {if (h < t) {t--;}return deque[t];
}
int isEmpty() { return h == t; 
}
void push(int x) { deque[t++] = x; 
}
int peek(){return deque[t-1];
}
int poll(){return deque[h++];
}
int main(){
//操作，如while(h<t&&deque[t-1]<nums[i]){t--；}
}

示例：

239. 滑動(dòng)窗口最大值 - 力扣（LeetCode）

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] deque = new int[nums.length];int h = 0, t = 0;for (int i = 0; i < k - 1; i++) {while (h < t && nums[deque[t - 1]] <= nums[i]) {t--;}deque[t++] = i;}int x = nums.length - k + 1;int[] ans = new int[x];for (int l = 0, r = k - 1; l < nums.length - k + 1; l++, r++) {while (h < t && nums[deque[t - 1]] <= nums[r]) {t--;}deque[t++] = r;ans[l] = nums[deque[h]];if (deque[h] == l) {h++;}}return ans;}
}

// 定義一個(gè)指向整數(shù)的指針數(shù)組，用于存儲(chǔ)滑動(dòng)窗口中元素的索引
int deque[numsSize];// 初始化頭部和尾部索引
int h = 0, t = 0;// 填充雙端隊(duì)列的前 k-1 個(gè)元素
for (int i = 0; i < k - 1; i++) {// 維護(hù)雙端隊(duì)列的單調(diào)性：移除所有比當(dāng)前元素小的元素while (h < t && nums[deque[t - 1]] <= nums[i]) {t--;}// 將當(dāng)前元素的索引加入到雙端隊(duì)列中deque[t++] = i;
}// 分配內(nèi)存用于存儲(chǔ)滑動(dòng)窗口最大值的結(jié)果
int* ans = (int*)malloc(sizeof(int) * (numsSize - k + 1));// 滑動(dòng)窗口遍歷整個(gè)數(shù)組
for (int l = 0, r = k - 1; l < numsSize - k + 1; l++, r++) {// 維護(hù)雙端隊(duì)列的單調(diào)性：移除所有比當(dāng)前元素小的元素while (h < t && nums[deque[t - 1]] <= nums[r]) {t--;}// 將當(dāng)前窗口的最后一個(gè)元素的索引加入到雙端隊(duì)列中deque[t++] = r;// 當(dāng)前窗口的最大值是雙端隊(duì)列頭部元素對(duì)應(yīng)的值ans[l] = nums[deque[h]];// 如果雙端隊(duì)列頭部元素的索引正好是窗口左邊界，則移除頭部元素if (deque[h] == l) {h++;}
}// 更新返回的最大值數(shù)組的大小
*returnSize = numsSize - k + 1;// 返回結(jié)果數(shù)組
return ans;

862. 和至少為 K 的最短子數(shù)組 - 力扣（LeetCode）

class Solution {// 初始化ans為一個(gè)較大的數(shù)值，以便在遍歷過(guò)程中找到更小的值int ans = 100001;public int shortestSubarray(int[] nums, int k) {// deque數(shù)組用于存儲(chǔ)當(dāng)前考慮的子數(shù)組的索引，實(shí)現(xiàn)單調(diào)隊(duì)列的功能int[] deque = new int[nums.length + 1];// 初始化雙端隊(duì)列的頭和尾索引int h = 0, t = 0;// sum數(shù)組用于存儲(chǔ)前綴和，sum[i]表示nums從0到i的元素和long[] sum = new long[nums.length + 1];// 初始化前綴和數(shù)組的第一個(gè)元素為0sum[0] = 0;// 循環(huán)遍歷數(shù)組numsfor (int i = 0; i <= nums.length; i++) {// 如果不是第一個(gè)元素，計(jì)算當(dāng)前位置的前綴和if (i != 0)sum[i] = sum[i - 1] + nums[i - 1];// 維護(hù)單調(diào)隊(duì)列：移除所有使得sum[i] - sum[deque[h]] >= k的元素// 因?yàn)檫@些元素之前的子數(shù)組和已經(jīng)不可能滿足和至少為kwhile (h < t && sum[i] - sum[deque[h]] >= k) {ans = Math.min(ans, i - deque[h++]); // 更新最短子數(shù)組長(zhǎng)度}// 維護(hù)單調(diào)隊(duì)列：移除所有使得sum[i] <= sum[deque[t - 1]]的元素// 因?yàn)檫@些元素對(duì)于找到和至少為k的最短子數(shù)組沒(méi)有幫助while (h < t && sum[i] <= sum[deque[t - 1]]) {t--; // 移除隊(duì)尾元素}// 將當(dāng)前元素的索引加入到單調(diào)隊(duì)列中deque[t++] = i;}// 如果ans沒(méi)有被更新，則說(shuō)明不存在和至少為k的子數(shù)組，返回-1return ans > 100000 ? -1 : ans;}
}

結(jié)語(yǔ)

單調(diào)隊(duì)列是一種強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，它在處理與窗口相關(guān)的算法問(wèn)題時(shí)特別有用。通過(guò)維護(hù)隊(duì)列的單調(diào)性，我們可以有效地減少不必要的計(jì)算，提高算法的效率。

希望這篇博客能夠幫助您更好地理解單調(diào)隊(duì)列以及如何在Java中實(shí)現(xiàn)和應(yīng)用它。如果您有任何問(wèn)題或想要了解更多信息，請(qǐng)?jiān)谠u(píng)論區(qū)告訴我。