>視頻講解：https://www.bilibili.com/video/BV1db411f7M7

最近在leetcode遇到一道非常經(jīng)典的題目：(https://leetcode.cn/problems/sliding-window-maximum/)

以前只會(huì)看題解用單調(diào)隊(duì)列做，最近研究一下發(fā)現(xiàn)是一道很好的題，可以幫助我們提升“維護(hù)區(qū)間最值”的算法思維。

先介紹一下我解決這題所用的算法及其復(fù)雜度：

* 單調(diào)隊(duì)列 $O(n)$

* st表 $O(nlogn)$

* 樹(shù)狀數(shù)組 $O(n(logn)^2)$

* 多重集合法$ O(nlogn)$

* 莫隊(duì)$O (n sqrt{n})$

* 優(yōu)先隊(duì)列 $ O(nlogn) $

首先確定一點(diǎn)，單調(diào)隊(duì)列是解決這道題最好的辦法，但是其他的方法的適用范圍更廣。

1、單調(diào)隊(duì)列

首先可以參考幾篇優(yōu)秀的文章：

算法學(xué)習(xí)筆記(66): 單調(diào)隊(duì)列 - 知乎 (zhihu.com)

單調(diào)隊(duì)列 - OI Wiki (oi-wiki.org)

我這里提幾點(diǎn)值得注意的地方：

1.單調(diào)隊(duì)列中存放的是下標(biāo)，而不是元素值

2.單調(diào)隊(duì)列是一個(gè)雙端隊(duì)列，尾插前先查隊(duì)頭后查隊(duì)尾

3.單調(diào)隊(duì)列維護(hù)的是元素值的單調(diào)性

有了這幾點(diǎn)注意，代碼就很好寫(xiě)了：

我做題習(xí)慣把輸入數(shù)組存一個(gè)array，大家請(qǐng)勿介意。

2.st表

st表是一種基于DP（動(dòng)態(tài)規(guī)劃）思想的算法，也算是一種數(shù)據(jù)結(jié)構(gòu)吧。

st表可以靜態(tài)維護(hù)區(qū)間的最值，需要用的時(shí)間來(lái)預(yù)處理，后可以O(shè)(1)查詢(xún)。

我們定義dp[i][j]表示

表示區(qū)間的最值，在這道題里我們認(rèn)為是最大值（維護(hù)最小值同理）。看一下能不能開(kāi)下，大概是maxn * 20的大小，可以開(kāi)下。

通過(guò)定義不難發(fā)現(xiàn)，dp[i][0] = a[i]，因?yàn)榇藭r(shí)區(qū)間長(zhǎng)度為1，那么最值就是元素a[i]本身。當(dāng)j增大時(shí)，我們有轉(zhuǎn)移方程（具體的原因可簡(jiǎn)單自行推導(dǎo)，以后的文章中也會(huì)有講解）：

dp[i][j] = max(dp[i][j - 1], dp[i + 2^(j-1)][j - 1])

查詢(xún)十分方便，方法是從兩邊往中間盡可能多地覆蓋。假設(shè)要查詢(xún)的區(qū)間是[l,r]

，那么我們可以得到區(qū)間長(zhǎng)度r - l + 1，現(xiàn)在求一個(gè)比長(zhǎng)度小且最大的2的冪，然后把左右兩塊取大即可。

直接看代碼：

3、樹(shù)狀數(shù)組

看見(jiàn)樹(shù)狀數(shù)組可能有小朋友會(huì)感到疑惑了哦，樹(shù)狀數(shù)組不是維護(hù)區(qū)間和的嗎？怎么還來(lái)湊“區(qū)間最值”的熱鬧了。

其實(shí)樹(shù)狀數(shù)組不僅可以維護(hù)區(qū)間和，還可以“動(dòng)態(tài)維護(hù)區(qū)間最值”，但是維護(hù)的方法和區(qū)間和略有不同。這一次主要看一下代碼吧，具體的原理之后再講。

樹(shù)狀數(shù)組節(jié)點(diǎn)t[k]維護(hù)的是區(qū)間[k - lowbit(k) + 1, k]。

樹(shù)狀數(shù)組主要突出的優(yōu)點(diǎn)就是可以動(dòng)態(tài)維護(hù)，但是注意在維護(hù)區(qū)間最值的時(shí)候僅可單點(diǎn)修改，不支持區(qū)間修改。

4、多重集合法

這種方法就十分簡(jiǎn)單粗暴了，就是維護(hù)一個(gè)不斷移動(dòng)的multiset，簡(jiǎn)直是暴力之王。

5、莫隊(duì)

莫隊(duì)需要基于multiset，在這道題里的優(yōu)勢(shì)并不明顯，因?yàn)檫@題的詢(xún)問(wèn)都是有順序的，但是可以寫(xiě)個(gè)莫隊(duì)練個(gè)手。

莫隊(duì)在處理隨機(jī)區(qū)間查詢(xún)問(wèn)題的時(shí)候有獨(dú)特的優(yōu)勢(shì)，因?yàn)樽銐虮┝Γ跃S護(hù)的東西可以很多很雜，比如區(qū)間和，區(qū)間最值，區(qū)間元素種類(lèi)數(shù)等。

以后我會(huì)詳細(xì)講莫隊(duì)的，歡迎大家在右上角留下郵箱訂閱我的博客(https://www.eriktse.com)，每周更新優(yōu)質(zhì)的算法/技術(shù)/互聯(lián)網(wǎng)文章！

6、優(yōu)先隊(duì)列

優(yōu)先隊(duì)列可以理解為一個(gè)“堆”結(jié)構(gòu)。

我們知道優(yōu)先隊(duì)列可以維護(hù)最值，但是他只有一個(gè)堆頂怎么辦呢？

我們只能保證堆頂是最大值但是卻無(wú)法保證堆頂是在窗口內(nèi)的呀！

為了解決這個(gè)問(wèn)題，我們?cè)诿恳淮尾樵?xún)堆頂之前，都要對(duì)堆頂進(jìn)行檢查，直到堆頂在窗口內(nèi)才能輸出。

注意以下幾點(diǎn)：

1.堆里存放的是下標(biāo)，但是比較函數(shù)用值比較。

2.每次取出元素之前堆頂檢查，只要堆頂?shù)奈恢貌辉诖翱趦?nèi)就一直彈出。

上代碼！