# Python-LeetCode 581 第10招 單調隊列 Monotonic stack and deque
## 基本原理
算法的效率來自
1. 避免不必要的計算
2. 避免重複的計算
例如大小關係的遞移性。若已知$a < b$與$b < c$，那麼不需比較我們就可以知道$a < c$。
貪心法則通常是找到強烈的性質來避免不必要的計算。但有時候性質沒有那麼強，我們無法立刻做決策，但可以維護其某些單調性，減少後面決策時不必要的計算。
本單元介紹某一類題型可以藉由維護一個單調的(子)序列，以避免一些不必要的計算，因而導致一個有效率的算法。這一類的題型進一步可分為兩種：monotonic stack與monotonic deque (queue)。
### 典型monotonic stack
Monotonic stack比較簡單，但兩者原理十分相似，以下我們先說明monotonic stack。基本型的操作很簡單：我們要用stack維護好一個單調遞減的序列，當下一個數字$s$到來時：
1. 將stack中小於等於$s$的全部pop掉；
2. 將$s$加入stack中。
操作的結果會繼續維持一個遞減序列。來看下面的經典裸題。
**Next greater element**
問題是：給一個數列$A[]$，對其中的每一個元素$A[i]$，找到其右方第一個大於$A[i]$的數字$A[j]$。
如果每一個數字的獨立的往右找，那麼可能會耗費$O(n^2)$的時間，例如$8,7,6,5,4,3,2,1,9$這個數列。
考慮以下做法。
我們從左往右，想像數字一個個進來。若容器$B$內裝著的是目前尚未找到Next greater的元素，現在進來的是$s$，那麼，依照定義，$B$中$<s$的元素的Next greater element就是$s$。再者，$B$中的元素都是尚未找到Next greater element的，所以他們從左到右必然是個遞減(非遞增)子序列，否則不會還沒找到。
所以，要找到$B$中所有小於$s$的元素只需**從後往前**一一比較就可以了：遇到小於$s$的，就設定他的next greater elemnet為$s$並從$B$中刪除，如果碰到$\geq s$的，就結束這一回合，因為$B$中剩下的也都$\geq s$。
在以上過程中，我們永遠只對容器$B$的最後一個元素進行比較或是刪除，結論就是，用一個stack來存放$B$就可以了。
我們看以下例題。
[(題目連結)496. Next Greater Element I (Easy)](https://leetcode.com/problems/next-greater-element-i/)
題目有一點變化。給兩個數列$nums1$是$nums2$的子集合，兩個數列中都沒有重複的數字。對於每一個$nums1[i]$要找這個數字在$nums2$中的next greater element。
因為$nums1$也可能等於$nums2$，所以就是要求出$nums2$所有數字的next greater element，我們用字典紀錄計算結果，$nums1$看成是query就好。
以下是範例程式。第3行初始一個stack，裡面放一個極大值當哨兵，用以減少空堆疊的檢查。第4行是一個字典，用來記錄next greater element計算結果，第5 ~ 8行就是前面介紹過維護堆疊的操作方法，本題中沒有相同數字，所以$<$與$<=$都一樣。第9行的while是因為殘留在stack中的元素是沒有next greater element的，依照題目規定給-1。時間複雜度$O(n)$。
```python=
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stk = [10001] # sentine
d = {}
for s in nums2:
while stk[-1] < s:
d[stk.pop()] = s
stk.append(s)
while len(stk)>1: # remaining
d[stk.pop()] = -1
ans = [d[x] for x in nums1]
return ans
```
### 典型monotonic deque
與monotonic stack不同之處在於，在deque的題型中，前方的元素可能因為**過期而失效**，所以需要把它移除。這個狀況是不出現在前面stack題型中的。
以下是曾經在[Python-LeetCode 581 第四招 前綴和 Prefix Sum](/OK7eUkz3SAuStSuhJu_Auw)中拿出來舉例說明的題目，是**單調隊列基本型範例**
[(題目連結)239. Sliding Window Maximum (hard)](https://leetcode.com/problems/sliding-window-maximum/)
題目說有一個長度為$k$的sliding window在一序列中一步一步移動，請計算出在每一個位置時的區間最大值。題目名稱有sliding window，但並非用該技巧。
其實要算的是$[max(nums[0:k])), max(nums[1:k+1]),\ldots ]$，也就是所有$n-k+1$個長度為$k$的區間的每一個區間最大值。當然，直接這麼寫的時間複雜度是$O(kn)$，太慢了。
單調隊列背後的道理可以以下面情境來打個比方。
「學生一屆一屆的進入學校，小明很喜歡程式比賽，當他進入學校時，如果有學長姐厲害到小明難以超越，那沒關係，小明在學校還是有出頭之日，因為學長姐會比他先畢業。但如果在小明之後新進來一位他無法超越的學弟妹，那完蛋了，小明在該校沒有什麼機會獨領風騷了，因為他會先畢業。」
我們的window在序列一步一步右移，可以看成一屆有一位學生進入，視窗長度固定為$k$，也就是學生進入後$k$屆就會畢業，同時在校的也恰有$k$位，我們要找出每一年最厲害的校內冠軍。
上面的例子告訴我們，對於某個$i$(小明)，如果同時在視窗內有個$j$，$nums[j]>nums[i]$，如果$j<i$，則 $i$ 尚未絕望，將來還有可能有機會當冠軍；但如果$j>i$，則 $i$ 從此刻起永遠不會是校內冠軍了。
如果我們把視窗內這些不可能成為冠軍的去除不看，那麼視窗內的將是個單調下降的子序列(monotonically decreasing subsequene)。這就是**單調隊列**。
我們用一個容器存放目前的隊列，維護的迴圈不變性是：
1. 隊列是遞減的
2. 隊列中均為尚在範圍內的元素
請注意，**根據迴圈不變性，隊列最前方的就是區間最大值**。每次新元素進入時，我們做兩件事：
1. 新生刪除所有不比自己強的學長姐。根據迴圈不變性，隊列為遞減的，我們只要從後往前刪除比新元素小的成員，當碰到第一個大於他的元素，刪除動作即已完成，因為前面的更大。刪除完成後再將自己加入隊列尾端(新生永遠有希望)。
2. 檢查最前方，也就是最大的元素是否已經出界，若是，將其移除。
要使用什麼容器來存放隊列呢？因為要支援前方與後方的移除，典型的做法是用deque (double ended queue雙向佇列)。Python也有提供deque，我個人比較喜歡用list加上一個head變數記錄頭端的位置即可。因為list尾端的刪除與新增都是$O(1)$，所以很方便。
來看本題的範例程式。
```python=
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = [] # (value,index) decreasing subsequence
head = 0
ans = []
for i,x in enumerate(nums):
while head<len(q) and q[-1] < (x,i):
q.pop()
q.append((x,i))
if q[head][1] <= i-k: # remove out of date
head += 1
if i>=k-1: ans.append(q[head][0])
return ans
```
因為需要偵測出界，這裡隊列的每個成員我們用一個tuple來存他的值與位置。當然也可以只存index然後用原陣列去抓值，也可以用兩個list。第6行逐一掃瞄新進成員，第7 ~ 8行執行尾端刪除，第9行將新進成員尾端加入，第10 ~ 11行檢查前端是否出界。
時間複雜度：$O(n)$，線性。
## Monotonic Stack的例題
給一個整數陣列，要計算出每一個可能子陣列最小元素的總和。
[(題目連結) 907. Sum of Subarray Minimums (Medium)](https://leetcode.com/problems/sum-of-subarray-minimums/)
題目要求的是
```python
sum(min(arr[i:j]) for i in range(len(arr)) \
for j in range(i+1,len(arr)+1))
```
當然這麼寫會TLE，一個長度為$n$的陣列有$O(n^2)$個子陣列，每個子陣列用min求最小值，這樣寫的時間複雜度是$O(n^3)$，我們必須找更好的方法。
直覺的想法是求出每個子陣列的最小值，但我們也可以將角色交換，**找出每個元素是哪些子陣列的最小值**。如果$arr[i]$是$p[i]$個子陣列的最小值，那答案也可以計算為$\sum_{i}arr[i]*p[i]$。那麼，問題變成要如算計算$p[i]$。
首先$arr[i:i+1]$這個子陣列只含$arr[i]$，所以它的最小值當然就是。如果最小值要是$arr[i]$，當然這個子陣列必須包含$arr[i]$，所以它可能的左端必落在$[0,i]$區間，而他的右端必落在$[i,n-1]$。我們算出左端的可能數量與右端的可能數量，兩者乘起來就是答案。
我們從$i$往前走，當到達甚麼樣的值區間最小值會變成不是$arr[i:i+1]$呢？這樣一想就清楚了，左端的邊界是$i$前方比$i$小的數字，也就是previous smaller element，相似的，右端的邊界就是next smaller element。
這裡有一個細節，當相同元素時，定義哪一個當最小都可以，但是不要重複都算就行了，下面的範例程式是算在比較前面的元素。
前面我們已經看過用stack求出next greater element的方法，求previous/next與smaller/greater都是類似的，所以我們可以跑兩次。事實上，跑一次就可以了。
以下是範例程式。第9行開兩個list存previous/next smaller的index，用堆疊維護一個非遞減序列，初始時底部放一個最小值當哨兵。第11行開始掃描陣列，當堆疊頂端較小時，$i$就是他的next smaller；當較小值pop完畢後，堆疊頂端的就是$i$的previous smaller。
當掃描完畢時，堆疊內可能還有元素，這些元素沒有next smaller，我們一開始已預設為$n$，所以不必再做任何處理。第18行算答案，第19行輸出。時間複雜度$O(n)$，因為根據amortized analysis，所有元素進出堆疊僅一次。
如果還不清楚此處單調stack的操作與原理，最好再回去看前面的典型範例說明。
```python=
class Solution:
# find the num of subarray [left,right] whose min is arr[i]
# num of left = i - idx of previous smaller
# num of right = idx of nxt smaller - i
# maintain non-decreasing subsequence
def sumSubarrayMins(self, arr: List[int]) -> int:
n = len(arr)
# inde of previous/next smaller
pSmall, nSmall = [-1]*n, [n]*n
stk = [(-1,-1)] # (val, idx)
for i,p in enumerate(arr):
while stk[-1] > (p,i): # i is next smaller
nSmall[stk[-1][1]] = i
stk.pop()
pSmall[i] = stk[-1][1] # my previous smaller
stk.append((p,i))
# result
total = sum((i-pSmall[i])*(nSmall[i]-i)*p for i,p in enumerate(arr))
return total%(10**9+7)
```
下一題直方圖的面積是很經典的題目。
[(題目連結) 84. Largest Rectangle in Histogram (Hard)](https://leetcode.com/problems/largest-rectangle-in-histogram/)
給一個直方圖(Histogram)，也就是寬度均為1的一些底部並列在一條水平線的矩形，要求出落在直方圖內部的最大矩形的面積，請參見下圖。
落在直方圖內的矩形也就是要選取一個連續區間$[i:j]$，其面積是$(j-i)\times min(h[i:j])$。
這麼一說，這題跟前面的子陣列最小值總和就十分相像。我們顛倒腳色，去算以$h[i]$為高度的最大矩形，也就是$h[i]$的previous smaller到next smaller之間的水平位置。對所有可能高度算出一個矩形，取最大值就是答案。
下面是一個範例程式，用stack維護一個increasing subsequence，previous/next smaller不必另外存，當遇到next smaller時，從stack pop出來，他的previous smaller此時就在stack的頂端。
時間複雜度$O(n)$。
```python=
class Solution:
# for h[i] the max rectangle with h[i] as height is
# from previous smaller to next smaller
# maintain increasing subsequence
# previous smaller is previous in stack
# compute the area when next smaller apper
def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0)
stk = [(-1,-1)] #stack
# find the max area with height[i] as the right side
max_area = 0
for i,h in enumerate(heights):
while stk[-1][0]>=h:
ih,_ = stk.pop() # i is next smaller of ih
max_area = max(max_area, ih*(i-stk[-1][1]-1))
stk.append((h,i))
return max_area
```
下面一題與前一題有點像，給一個0/1矩陣，找出1構成的最大矩形面積。
[(題目連結) 85. Maximal Rectangle (Hard)](https://leetcode.com/problems/maximal-rectangle/)
確實與直方圖面積非常像。想像第$i$ ~ $j$列的區間，水平看過去，對於每一欄，如果這些列都是1，就相當於直方圖中一個高度$j-i+1$的矩形bar，否則(不是全1)，就將高度設為0。轉換後求直方圖面積即可。
對於$m\times n$的矩陣，要枚舉所有列區間，我們妥善安排順序，每一個區間的轉換只花$O(n)$的時間，直方圖求面積也只花$O(n)$的時間，整體時間複雜度就是$O(m^2 n)$。
```python=
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m,n = len(matrix),len(matrix[0])
def Area(heights):
heights.append(0)
stk = [(-1,-1)] #stack
# find the max area with height[i] as the right side
max_area = 0
for i,h in enumerate(heights):
while stk[-1][0]>=h:
ih,_ = stk.pop()
max_area = max(max_area, ih*(i-stk[-1][1]-1))
stk.append((h,i))
return max_area
#main
h = [0]*n
ans = 0
for i in range(m):
for j in range(n):
if matrix[i][j]=="1":
h[j] += 1
else:
h[j] = 0
ans = max(ans, Area(h))
#end for
return ans
```
[(題目連結) 1944. Number of Visible People in a Queue (Hard)](https://leetcode.com/problems/number-of-visible-people-in-a-queue/)
題目是說有$n$個人從左到右排成一列，給定每個人的高度，要計算每個人往右看過去可以看到幾個人，第$i$個人看得到第$j$個人的定義是兩人之間的人都比他們矮，$h[k]<min(h[i],h[j])$ for all $i<k<j$。
對於任何一個人$j$來說，如果他的左方出現一個$\geq h[j]$的人，他就會被**屏蔽**了，也就是不可能被更左方的人看到。所以我們如果從右往左掃過來，刪除沒有用的(被屏蔽而不會再被看到的)，只需維護一個(左到右)遞增序列就可以。當我們掃到$i$時，他看到的人就是這個遞增序列中$<h[i]$的人以及第一個$\geq h[i]$的人。從前面所用的術語來說，事實上，就是以$i$為previous greater的人，以及$i$的next greater (相等納入)，
所以程式跟前面的範例也很像。
```python=
class Solution:
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
n = len(heights)
ans = [0]*n
stk = [100001]
i = n-1
for h in heights[::-1]:
cnt = 0
while stk[-1]<h:
cnt += 1
stk.pop()
ans[i] = cnt+int(len(stk)>1)
stk.append(h)
i -= 1
return ans
```
[(題目連結) 1776. Car Fleet II (Hard)](https://leetcode.com/problems/car-fleet-ii/)
有$n$部車在同一條路上同方向前進，第$i$部車的速度是$s_i$，編號越大的車的起始位置在越前面，後方車如果追上前方車，就會形成一個集團，集團以前方車的速度繼續往前。所有車在時間0時開始前進，請計算出每一台車追上前一台車的時間，如果不會追上則以-1表示。
每台車在追上前車之前是等速前進，追上前車後變成前車的速度繼續等速前進，所以每一台車全程的速度是一個**piecewised linear**函數，其斜率(速度)為遞減，如下圖。
我們由前往後(編號由大到小)一一算出車子的速度函數，第$i$車的每一段速度就存在一個stack中，考慮第$i-1$台車時，從stack上方開始一一計算該轉折點是否追上前車，若否，則將該資料pop刪掉；如果追上時，就計算出追上的點，該點必位於此點與前一點之間，如下圖所示。如果始終都沒追上前車，會將前車的速度完全pop掉，此時在stack中加上本車的初始速度就可以了。
這樣我們不僅算出第$i-1$台車追上前車的時間，也將第$i$台車的速度(piecewised linear function)更新為第$i-1$的速度。
在程式中，為方便表示，我們設一個無限大的距離。每一個速度轉折點存3個資料，時間、速度、以及距離，表示在此距離在此時間之前是以該速度前進，也就是前面圖中每一段的斜率。
第9行開始掃描每一台車，用while迴圈pop掉沒有追上的轉折點。第12行是stack全部pop到空的狀況，此時重新加上這一台車的速度；否則，我們要計算出追上的時間與位置(第16行)。最後的答案增加一個-1是因為第一台車(編號最大)是沒有前車可以追的。
```python=
class Solution:
# piecewised linear in stack
def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
ans = []
oo = 10**13
cars = cars[::-1]
# (time, speed before distance, distance)
stk = [((oo-cars[0][0])/cars[0][1],cars[0][1],oo)]
for p,s in cars[1:]:
while stk and (stk[-1][2]-p)/s >= stk[-1][0]:
stk.pop()
if not stk:
ans.append(-1)
stk.append(((oo-p)/s,s,oo))
else: # t*s+p = pi-si*(ti-t),
t = (stk[-1][2]-p-stk[-1][1]*stk[-1][0])/(s-stk[-1][1])
ans.append(t)
stk.append((t,s,t*s+p))
ans = ans[::-1] + [-1]
return ans
```
[(題目連結) 1856. Maximum Subarray Min-Product (Medium)](https://leetcode.com/problems/maximum-subarray-min-product/)
給一個正整數的陣列，要找出一個子陣列(連續區段)，該子陣列的最小值與總和的乘積越大越好。
對於一個點$nums[i]=p$，我們往左找到第一個$nums[j]<p$，也就是previous smaller；往右找第一個$nums[k]<p$，也就是next smaller。那麼$[j+1,k-1]$這個區間就是以$nums[i]$為最小值的最大區間。對每一個$nums[i]$都找此最大區間的總和乘積，在求出其中最大的就是答案。
結論是這題也是要找previous/next smaller，為了計算區間總和，我們利用prefix sum。
以下為範例程式。psum是用來算prefix sum，我們一面走一面算，需要的值存在stack中。inc是我們的stack，用來存遞增子序列，每一個元素是(某點的值，某點的前綴和)。我們在堆疊底部放個無限小的-1，掃描陣列的尾端放個0，都是用來當哨兵簡化程式。
當$p$進來時，我們計算處理以$p$為next smaller的元素(等號包含)。它的previous smaller就在堆疊中，因此我們很容易計算以它為最小值的最大區間(第11行)。
時間複雜度$O(n)$。
```python=
class Solution:
# using stack maintaining increasing subsequence
def maxSumMinProduct(self, nums: List[int]) -> int:
n = len(nums)
psum = 0 # prefix sum
inc = [(-1,0)] # stack (val,sum), sentinel
imax = 0
for p in nums+[0]: #sentinel to clear remaining
while inc[-1][0] >= p: # p as the right boundary
imin = inc.pop()[0]
curr = imin*(psum-inc[-1][1])
imax = max(imax, curr)
psum += p
inc.append((p,psum))
#
return imax%1000000007
```
### Tree的題型
[(題目連結) 1130. Minimum Cost Tree From Leaf Values (Medium)](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/)
給一個正整數序列，要建構一個二元樹，其每個中間節點都恰有兩個孩子，而葉節點由左而右恰為所給的正整數序列，在滿足此要求的二元樹之中，希望找到中間節點的總和最小的，而中間節點的值定義為其左右子樹中最大的葉節點之值的乘積。
以下圖為例，輸入序列為$[6,2,4]$，可能的二元樹只有兩棵，圖右的中間節點總和較小，所以答案是8+24=32。
上面的例子透漏了解題的可能方向。這題可以歸類在Greedy，但其做法是維護一個decreasing stack，所以歸在本單元也可以。
二元樹由底層往上，可以看成一個合併的過程。在上例中，關鍵在於2要先跟前面的6合併，還是先跟後面的4合併，而我們可以看到它所影響的就是2與其他節點合併的中間節點的值，所以它跟比較小的(4<6)合併會導致比較小的解。
因為中間節點的值是取左右的最大葉節點來相乘，所以一個數字一旦與一個比較大的數字合併後，再往上走它就沒有扮演腳色了，所以我們可以想像成**一個數字將會跟一個比較大的數字合併並消失**。那麼，它跟哪個數字合併最好呢？不難看出就是跟previous greater與next greater之中較小的合併最好，難道不會是其他的節點嗎？如果next greater先跟更後面的合併，那結果只會更大或一樣，所以跟更後面或更前面的合併不會比較好。
結論是**每個節點應該跟previous greater與next greater中較小的合併**。
和前面的範例類似，做法就是用一個stack維護遞減序列，堆疊內的前一個就是prevous greater，當遇到next greater的時候就可以決定一個元素要跟誰合併了。
以下是範例程式。相似的，我們在堆疊內放一個極大的值當作哨兵，掃描序列。第8行的while迴圈是進來的元素是next greater的狀況，我們將堆疊top元素pop出來，算它要跟前或後合併，處理完畢後，再將p塞入堆疊中維持一個遞減序列。
最後當掃描完畢後，堆疊內可能殘留一個遞減序列，我們要將每一個併入前一個(previous greater)，直到剩下一個為止。
時間複雜度$O(n)$。
```python=
class Solution:
# O(n) greedy; each element is removed and merged with the
# smaller of its left/right greater
def mctFromLeafValues(self, arr: List[int]) -> int:
stk = [10**9] # a decreasing subsequence
ans = 0
for p in arr:
while stk[-1] <= p:
q = stk.pop()
ans += q*min(p,stk[-1])
stk.append(p)
#
while len(stk) > 2:
q = stk.pop()
ans += q*stk[-1]
return ans
```
[(題目連結) 654. Maximum Binary Tree (Medium)](https://leetcode.com/problems/maximum-binary-tree/)
給一個沒有重複數字的數列，要用以下的方法建構出一個binary tree。
1. 找出最大值當作root
2. 最大值左邊遞迴建構出左子樹
3. 最大值右邊遞迴建構出右子樹
根據這個定義直接做的話，會太耗時，因為最大值的切割可能很不平均，一個極端的例子是變成一條鍊。
從定義觀察，$v$點的右孩子如果是$u$，那麼，$v$必然在$u$的左邊而且$v>u$。更進一步，$v$與$u$之間不可能有大於$v$或$u$的點，否則$u$不會是$v$右子樹中的最大。因此，$u$就是以$v$為previous greater的那些節點中最大的那一個，也就是最後一個。
類似的，$v$的左孩子就是以$v$為next greater那些節點中最大者，也就是最左邊的。
有了這樣的理解後，我們可以像求next greater的方式來決定每個點的左右孩子。以下是範例程式。
我們一樣用一個堆疊維護遞減序列，掃描到$v$時，堆疊中比它小的都是以它為next greater的點，我們不必管所謂的第一個，只要pop stack時把$v$的左孩子設為堆疊頂端的點，最後一個寫下去的就是所謂的第一個。相同的，堆疊pop完畢時，堆疊中的頂端($u$)就是$v$的previous greater，也就$u$的右孩子可能是$v$，一樣的，我們不需管$v$是否是最後一個以$u$為previous greater的點，我們只要寫下去，最後一個寫的就是最後一個，此處要注意，堆疊可能為空，也就是$v$沒有previous greater，所以要用if來檢查。
時間複雜度一樣是$O(n)$。另外要注意本題是規定用LeetCode提供的binary tree class，這一類的題目不少，只要看得懂，會初始節點，存取其中的欄位就可以了。
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# right child of v is the last vertex whose previous greater is v.
# # left child is the first whose next greater is v.
# stack keep decreasing subsequence
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
stk = [] # decreasing subsequence, right-most path of tree
for x in nums:
v = TreeNode(x)
while stk and stk[-1].val< x:
v.left = stk[-1]
stk.pop()
if stk:
stk[-1].right = v
stk.append(v)
#end for
return stk[0]
```
## Monotonic Deque or Queue的例題
[(題目連結) 1499. Max Value of Equation (Hard)](https://leetcode.com/problems/max-value-of-equation/)
給一個平面整數點座標的陣列與一個整數$k$，保證X座標為嚴格遞增。要找兩點$(x_i,y_i)$與$(x_j,y_j)$，滿足$|x_i-x_j|\leq k$，求目標函數$y_i+y_j+|x_i-x_j|$的最大值。
用白話講就是，X差值在給定$k$的範圍內，兩點Y座標與X差值之和的最大值。
枚舉所有點對的時間複雜度$O(n^2)$不能滿足效率的要求，必須找優化的方式。對於每一個$(x_i,y_i)$，我們找出最大化目標函數的$j<i$，對所有$i$再取最大值就是答案。
對於指定的$i$且限定$j<i$之後，目標函數簡化為
$$
\begin{split}
&\max_{j<i}\{y_i+y_j+|x_i-x_j|\} \\
&= \max_{j<i}\{y_j-x_j+(y_i+x_i)\} \\
&= \max_{j<i}\{y_j-x_j\} + (y_i+x_i)
\end{split}
$$
因為對指定的$i$，$x_i+y_i$為常數，我們只要求$y_j-x_j$的最大值就好了，當然是在題目要求的$x_i-x_j\leq k$ 的限制之下。
做法已經浮現了。我們由左往右掃過去，紀錄目前最大的$y_j-x_j$，如果後面出現的值比較大，前面的就沒有用了(請回想本單元前面所揭示的經典題)，但後面的值如果比較小，則仍需保留，因為前方的點會因為X範圍限制而出界。我們要保留的是一個$y_j-x_j$的遞減序列。
以下是範例程式，我們用一個list que搭配一個index head來做deque，每一個元素包含該點X與Y-X。第6行迴圈開始掃描歷遍，第7行檢查頭端元素是否已經過期出界，第9行若deque內有元素，取出頭端就是最大值。然後我們從deque的尾端檢查，刪除小於等於$y-x$元素(它們將不再有用)，維護好遞減序列。
時間複雜度$O(n)$。
```python=
class Solution:
# for each (x_i,y_i) find max{y_j-x_j: j<i and x_j>=x_i-k}
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
imax = -10**9
que = []; head = 0 # (x_i, yi-xi)
for x,y in points:
while head<len(que) and que[head][0]<x-k:
head += 1 # pop out of date
if head<len(que):
imax = max(imax, x+y+que[head][1])
t = y-x
while head<len(que) and que[-1][1]<=t:
que.pop()
que.append((x,t))
return imax
```
[(題目連結) 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Medium)](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/)
給一個正整數的陣列，以及一個非負整數$limit$。要找出最長的一段子陣列，在此子陣列中任兩個數字的差值皆不超過$limit$。
任兩個數字的差值皆不超過$limit$的意思其實就是最大值與最小值的差值不超過$limit$。我們可以搞一個sliding window，每次將右端推一格，然後很直白的調整左端。
```python=
left = longest = 0
for right in range(n): # try each right
while max(nums[left:right+1]) > min(nums[left:right+1])+limit:
left += 1
longest = max(longest,right-left+1)
```
這麼寫清楚是清楚，但時間複雜度很糟糕，對一個右端，可能嘗試各種左端，每次要花$O(right-left)$的時間算最大值與最小值，這樣$O(n^2)$少不了。
我們設法優化每次重新尋找區間最大值與最小值的部份，因為當右端移動一格時，區間的最大與最小的變化是有一些特性而非毫無脈絡的。
我們維護一個單調遞減序列qmax，可以找到最大值；再維護一個單調遞增序列qmin，可以找到最小值。對於每個右端$i$，我們先用while調整單調隊列，然後檢查是否調整左端，當最大值與最小值的差超過$limit$時，就要調整左端，調整時，看最大值與最小值哪一個出現在比較左邊，就先移除，直到區間內的差值在要求範圍內為止。
以下是範例程式，本題我們在單調隊列中放的是index，時間複雜度$O(n)$。
```python=
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
qmax, qmin = [0],[0] # dec and inc subsequence (index)
hmax,hmin = 0,0 # head of qmax and qmin
longest = 1
left = 0 # current left
for i,p in enumerate(nums[1:],start=1):
while hmax<len(qmax) and p>=nums[qmax[-1]]:
qmax.pop() # decreasing
qmax.append(i)
while hmin<len(qmin) and p<=nums[qmin[-1]]:
qmin.pop() # increasing
qmin.append(i)
# move left if >limit
while nums[qmax[hmax]] > nums[qmin[hmin]]+limit:
# remove max or min, which is left
if qmax[hmax] < qmin[hmin]:
left = qmax[hmax]+1
hmax += 1
else:
left = qmin[hmin]+1
hmin += 1
longest = max(longest,i-left+1)
return longest
```
這一題也有一個$O(n\log n)$的解。利用sliding window，我們可以在$O(n)$求出給定視窗長度$w$時，差值最小的視窗。因為視窗越長，最小差值必然單調非遞減，我們可以對答案進行二分搜。
## DP+單調隊列
[(題目連結) 1425. Constrained Subsequence Sum (Hard)](https://leetcode.com/problems/constrained-subsequence-sum/)
給一個數列以及一個正整數$k$，要選取一個總和最大的子序列，限制條件是子序列中兩個相鄰元素在原始數列中的位置不得超過$k$。也可以這樣看，你可以從序列的任何一個位置開始挑選，也可以隨時終止挑選，但挑於一個之後，與下一個之間的距離不可超過$k$。
如果$k=1$，就是必須挑選連續的一段，這是一個著名經典題max subarray，所以本題是max subarray的一個延伸題。
考慮DP吧！
設$dp[i]$是最後一個挑$i$的最大總和。因為前一個間距不能超過$k$，
$dp[i] = nums[i]+\max\{\max\{dp[j] \text{ for } i-k\leq j<i\},0\}$
與0取max是因為如果範圍內的值是負的，則不如拋棄重新開始挑選。
有了DP遞迴式之後就要看如何做了，這樣一個1d1d的DP，如果照遞迴式直接做，或需要$O(kn)$的時間複雜度，因為有$O(n)$要求，每個需要在$k$個中挑最大值。
跟前面的題目一樣，我們只需要維護DP值的單調下降序列就可以了，因為後面出現更大的DP值時，前面的就沒用了，此外，因為有距離的限制，要考慮目前的最大值可能出界，所以用一個單調隊列就簡單了。
以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
# dp[i] = nums[i]+max(dp[j] for i-k<=j<i)
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
t = max(nums)
if t<=0: return t
imax = 0
# que = decreasing subsequence of dp
que = [(0,-1)] # (dp, index)
head = 0
for i,p in enumerate(nums):
if que[head][1]<i-k:
head += 1 # out of date
t = max(que[head][0]+p,0)
while head < len(que) and que[-1][0]<=t:
que.pop() # pop useless
que.append((t,i))
if t>imax: imax = t
return imax
```
下一題有些類似。
[(題目連結) 1696. Jump Game VI (Medium)](https://leetcode.com/problems/jump-game-vi/)
給一個整數陣列與一個正整數$k$，要從陣列位置0的地方開始跳到最後一格，每次只能往前跳距離不超過$k$，採到的格子就是獲得的分數，要求最大得分總和。
令$dp[i]$是最後踩在$i$的最大得分總和，動態規劃的遞迴式是
$dp[i] = \max_{i-k\leq j<i}\{dp[j]\} + nums[i]$。
相同的，我們要優化選取區間最大值的方法。使用一個單調下降的隊列就可以做到了。
下面是範例程式，我們用deque來維護dp值單調遞減序列的index。時間複雜度$O(n)$。
```python=
class Solution:
# dp[i] = max(dp[i-k:i])+nums[i]
# deque for decreasing subsequence
def maxResult(self, nums: List[int], k: int) -> int:
n = len(nums)
d = deque([0]) # index of subsequence
dp = [0]*n
dp[0] = nums[0]
for i in range(1,n):
if d[0]<i-k: d.popleft()
dp[i] = dp[d[0]]+nums[i]
while d and dp[d[-1]] <= dp[i]:
d.pop()
d.append(i)
return dp[-1]
```
## 結語
Monotonic stack的題型大多是next greater element (NGE)的變化型，處理此問題時，我們掃描陣列，有些可以立刻決定NGE，但有些當下無法決定，但我們維護好一個遞減序列，在後續決策時省卻一些不必要的計算。我們可以再體會一下本單元開頭的那一段話，對算法的精神或許有進一步的體認。
單調隊列的DP優化是一個很經典的動態規劃題型，在需要區間極值的場合，也有另外的資料結構(Range maximum query, RMQ)可以協助處理，但會比較複雜，時間複雜度也可能差一些。單調隊列處理的是特殊的RMQ，它的區間是逐步滑動的一個特殊狀況，而非任意區間的查詢。
我們在後面的單元將會對DP有更多的介紹。
Sign in with Wallet
Connect another wallet