# AP325-Python 第3章 佇列與堆疊
想到堆疊，想到深度；想到深度就想到歐陽修這首蝶戀花：
「庭院深深深幾許，楊柳堆煙，簾幕無重數。玉勒雕鞍遊冶處，樓高不見章臺路。
雨橫風狂三月暮，門掩黃昏，無計留春住。淚眼問花花不語，亂紅飛過鞦韆去。」
關於窗戶：
「Where there’s will, there’s a way;
where there’s way, there’s a wall;
where there’s wall, there’s a window. 」
---
這一章介紹三個基本的資料結構：佇列(queue)、堆疊(stack)與雙向佇列(deque，念做 "deck"，正式名稱是double-ended queue)，除了說明基本原理與應用外，也介紹一種與雙向佇列類似的演算法：滑動視窗(sliding window)。另外我們也介紹單調隊列(monotonic queue)與鏈結串列(linked list)，前者是根據題目特性來維護一個單調序列以提高效率的方法，後者是一種在實際用途很廣，但是在解題上比較少用的資料結構。
這幾種資料結構都是課本上的基本資料結構，有很多應用。滑動視窗這個名字倒是有很多不同的稱呼方式，也有稱為爬行法，或認為是雙指針(two-pointers)方法的一種。反正名稱不是那麼重要，懂得原理與會運用才是最重要的事。我們先介紹基本原理與實作方式，然後再來看應用的題目。
## 基本原理與實作
佇列、堆疊與雙向佇列都是簡單的資料結構，簡單到可以自己用list實作，但也有庫存函數的容器可以使用，自己實作的在碰到空間問題時會比較麻煩，不過在解題的場合，很少會碰到空間問題，而且對於某些題目，自製的方式比較合適，這份講義中將以list自製的方式為主。
這三種資料結構都是"線性”的，可以在一維陣列實作。鏈結串列最大的優點是將線性的資料放在不連續的位置，這特性在實際系統與軟體中有時非常重要，也因如此，串列需要以指標與記憶體配置來搭配。但解題的場合很少有空間的問題，也幾乎都避免使用pointer，所以串列部分我們只說明解題中常見的方法。
### 佇列(queue)
佇列就好像是一群人排隊排成一列，有一個出口與一個入口，通常出口稱為前端(front, head)而入口稱謂後端(back, tail)。成員進入時只能從入口進入，也就是加入尾端；離開時只能依序從出口離開，佇列的特性是先進先出(FIFO, first-in first-out)。
Python的list與C的陣列不同，list的成員不必是相同的資料型態，但在實作資料結構的場合，每一筆資料是相同的樣子。佇列通常需要四個基本操作，新增、刪除、查看出口的成員、以及檢查是否為空，有時也會查詢目前成員數。
我們可以很簡單的以list來實作佇列，初始時是個空的list，並且用一個變數$head$來記錄頭端的位置(index)。每次加入時，用list.append()在尾端加入新成員；每次刪除時，將 head += 1，而不真正執行刪除的動作。
請注意，如果用list.pop(0)是可以把list最前端的元素刪除，但是**這個刪除動作的時間複雜度是list的長度**，所以除非queue很短，否則這樣做是不好的。
請看下面的範例程式展示著自製佇列的基本用法以及支援的四個操作。我們沿用常用的名詞，加入稱為push，刪除稱為pop，這名字其實來自堆疊。讀者可以執行此範例程式並輸入程式中的範例輸入來了解queue的運作。輸入資料有若干個命令，每個命令是push一個數字或是pop，程式讀取每一個命令，如果是push就將資料加入queue，如果是pop要先檢查佇列是否是空的，否則刪除資料並輸出。
```python=
# demo self-made queue
que = [] # initial empty queue
head = 0 # index of head
n = int(input())
for i in range(n):
cmd = input().split()
if cmd[0] == "push": # push t
que.append(cmd[1])
elif cmd[0] == "pop":
if head == len(que): # is empty?
print("empty\n")
else:
t = que[head] # pop to t
head += 1
print(t)
#
print("Current queue =",que[head:])
'''
sample test input
7
push 4
pop
pop
push 3
push 8
push 2
pop
'''
```
### 堆疊(Stack)
堆疊像是把子彈放入子彈夾(可能沒看過)，或者想像把硬幣堆疊在桌上。堆疊的出口與入口相同，就是最上面那一個，通常稱為top。成員進入時只能從上方壓入(往上疊)，稱為push；離開時只有頂端top的成員可以離開。堆疊的特性是後進先出(LIFO, last-in first-out)。在通常使用的堆疊中，所有的成員經常是相同的資料型態。堆疊通常需要四個基本操作，push、pop、查看top的成員、以及檢查是否為空。
以list來實作堆疊比佇列更簡單，因為只有一端開口，我們將堆疊的底部設在list開頭之處，top的位置就是list的最後一個元素list[-1]，每次push時就append；每次pop時，因為list.pop()預設是list.pop(-1)，所以就list.pop()就可以。在一連串操作時，堆疊只是list長度前後移動，像是一端黏在牆壁的彈簧。尤其list.pop(-1)與list.append()的時間複雜度都是$O(1)$，所以好用又快速。請看下面的範例程式，它的測試資料與佇列相同。不熟悉的讀者可以用範例程式來了解用法。
```python=
# demo self-made stack
stk = [] # initial empty stack
n = int(input())
for i in range(n):
cmd = input().split()
if cmd[0] == "push": # push t
stk.append(cmd[1])
elif cmd[0] == "pop":
if len(stk) == 0:
print("empty\n")
else:
t = stk.pop() # pop to t
print(t)
#
print("Current stk =",stk)
'''
test input
7
push 4
pop
pop
push 3
push 8
push 2
pop
'''
```
### 雙向佇列(deque)
如果了解了queue的操作之後，deque的操作就容易了解了，它與queue很類似，差異在它的前後都可以進出。自製一個完整功能的deque並不容易，標準函式庫中有deque()可以叫用。以下程式簡單示範常用功能。
```python=
# demo deque
from collections import deque
dque = deque() # initial empty deque
dque.append(1) # push from tail
dque.appendleft(2) # push from head
dque.appendleft(3) ; dque.appendleft(4)
print(dque, len(dque))
h = dque.popleft()
t = dque.pop()
print(h,t,dque)
print(dque[0], dque[-1])
```
自己用list製作deque的困難在於左端空間的問題，當然要做也並非不可能，只是比較麻煩。不過，算法上用到deque的時候，往往是不需要左端移除的功能，那麼，我們可以用製作queue的方式用一個list與一個變數head來製作deque。在後面的題目中會碰到，我們會再說明。
## 應用例題與習題
佇列、堆疊與雙向佇列常常是用其他演算法裡面做為一個基本步驟，單獨出現的不算太多。尤其單純queue的題目並不多，除非是簡單的操作模擬。但是在樹與圖的走訪卻是非常重要，這些要等到後續單元介紹了圖與樹的基本概念後再介紹比較合適。這裡提出一個例題，事實上是tree的題目，因為不需要太多專業術語，可以先放在此處當作queue的例題，等到後面的章節會再提出其他解法。
---
##### P-3-1. 樹的高度與根 (bottom-up) (APCS201710)
有一個大家族有$N$個成員，編號1 ~ $N$，我們請每個成員寫下此家族中哪幾位是他的孩子。我們要計算每個人有幾代的子孫，這個值稱為他在這個族譜中的高度，也就是說，編號 $i$ 的人如果高度記做 $h(i)$，那麼 $h(i)$ 就表示在所有 $i$ 的子孫中，最遠的子孫與他隔了幾代。本題假設除了最高的一位祖先(稱為root)之外，其他成員的parent都在此家族中(且只有一個parent)。本題要計算所有成員高度的總和以及根的編號。
上圖是一個例子，每個成員是一個圈起來的號碼，劃線相聯的表示上面的點是下面點的parent。編號4是根，有兩個孩子1與7。編號6, 9, 3, 8都沒有孩子，$h(6)=h(9)=h(3)=h(8)=0$，此外
$h(2)=2$因為9與他隔兩代。你可以看出來$h(5)=h(1)=1$，$h(7)=3$, $h(4)=4$，所以高度總和是11。
Time limit: 3秒
輸入格式：第一行有一個正整數 $N$。接下來有 $N$ 行，第 $i$ 行的第一個數字 $k$ 代表 $i$ 有 $k$ 個孩子，第 $i$ 行接下來的 $k$ 個數字就是孩子的編號。每一行的相鄰數字間以空白隔開。$N \le 1e5$。
輸出：第一行輸出根的編號，第二行輸出高度總和。
範例輸入：
9
1 6
3 5 3 8
0
2 1 7
1 9
0
1 2
0
0
範例結果：
4
11
---
沒有處理過樹狀圖的人可能會覺得這題複雜，但其實不難，這裡我們盡量不使用樹的術語來講。首先我們用個陣列把每個人的parent讀進來，第一個問題是如何找根。沒有parent的就是根，所以很簡單，只要看看哪個點沒有parent就行了。第二個問題要找高度，因為我們有每個點的parent，一個直覺的做法就是：
從每一個點 $i$ 出發，依據parent一直往上走直到無路可走(到達root)，並且用一個記步器 $cnt$ 記錄走了幾步。每到一個點 $j$，根據 $cnt$ 就可以知道 $i$ 是 $j$ 的第幾代子孫。因為高度是要取所有子孫離他最遠的，所以到達 $j$ 點時，就取$h[j]=\max(h[j],cnt)$；在所有的點都走完之後，各點的高度就已經算好了。
夠簡單吧！以下是這個解法的範例程式。
```python=
# tree height slow method O(nL), L=tree height
n = int(input()) #
parent = [-1]+[0]*n # parent of node i, 1-index
h = [0]*(n+1) # height of node i
for v in range(1, n+1):
for ch in [int(x) for x in input().split()][1:]:
# first is deg, useless
parent[ch] = v
root = parent.index(0) # the one witout parent
# [0] is useless, parent[0]=-1 to avoid to find 0
print(root)
for v in range(1,n+1): # each node
j = parent[v] # start from it parent
cnt = 1 # num of step from i
# go up until root
while j !=0 : # until upmost
h[j] = max(h[j], cnt) # max step from descendant
cnt += 1
j = parent[j]
#
total = sum(h)
print(total)
```
這程式雖然容易理解，答案跑出來也是對的，但是有個問題，跑太慢，他的複雜度是多少呢？以一個極端的例子來看，如果這個家族10萬個成員全部都是單傳，最高祖先的高度是99999，那麼這個程式的複雜度是多少呢？你或許會抗議哪裡有這麼多代的家族呀！唉呀，競賽程式就是這樣會給刁鑽的測資，worst case就真的很worst，況且題目根本沒說是人的家族，細菌10萬代就很有可能。好了，廢話少說，因為上面這個程式裡，每個點都要往上爬到根，所以在這個極端的例子裏，最下面的要跑99999，倒數第二的要跑99998，…，所以總共的複雜度約是1加到99999，複雜度是$O(n^2)$，3秒只能跑某些測資，有些測資是跑不完的。
找到問題就設法改善吧。程式跑太慢通常是做了太多重複的事，在前面這個10萬代單傳的例子裏，這個方法之所以慢，就是走了太多一樣的路：最下一層的往上爬了 $N$ 層，他的parent(倒數第二層)爬了 $N-1$ 層，兩位爬的路幾乎重複，假設倒數第二層確定知道自己的高度是1的話，那這兩位重疊的路只要爬一次不需要爬兩次。
也就是說，對於 $i$ 點，如果 $h[i]$ 已經確定，那麼 $i$ 的子孫不必每位都爬 $i$ 到根那段路，只要從 $i$ 的高度往上計算爬一次就好了。那麼，要如何確定 $i$ 的高度呢？根據定義，只要$i$ 的子孫都已經爬到 $i$ 點，$i$ 的高度就確知了。
因為子孫關係有遞移性，我們得到一個結論：如果我們可以調整計算的順序，使得「每個點都在他的所有孩子之後計算，那麼，每個點只需要向他的parent回報自己的高度就可以了」。
這樣一個順序我們稱為由下而上的順序(bottom-up sequence)。假設 $seq[]$ 存放著一個bottom-up順序，那麼，計算高度只需要以下簡單的程式碼：
```python
for v in seq:
h[parent[v]] = max(h[parent[v]], h[v]+1))
```
所以重點在於如何找出一個bottom-up順序，這就是queue出場的時候了，請看以下的算法。我們說**一個點可以離開是指他的孩子都已經離開**，顯然這樣的離開順序是一個bottom-up sequence，以下是計算一個bottom-up順序的方法。
>對所有 $v$，以 $deg[v]$ 紀錄 $v$ 目前還在的孩子數量，以一個queue $que$放置所有可以離開但尚未離開的點。一開始把所有 $deg$ 為0的點放入 $que$ 中。每次從 $que$ 中拿出一個點 $v$，讓 $v$ 離開，更新他parent的 $deg$，如果他parent的 $deg$ 降為0，就將他parent放入 $que$。
結合這樣的順序，我們可以將上面的程式改成下面的範例程式，另外我們也不需要特別去找root，因為bottom-up順序的最後一個必然是root。
```python=
# tree height O(n), bottom-up
n = int(input()) #
parent = [-1]+[0]*n # parent of node i, 1-index
h = [0]*(n+1) # height of node i
deg = [0]*(n+1) # num of child
for v in range(1, n+1):
child = [int(x) for x in input().split()]
# first is deg, useless
deg[v] = len(child)-1
for ch in child[1:]:
parent[ch] = v
# initial que with deg==0
que = [v for v in range(1,n+1) if deg[v]==0]
head = 0
total = 0 # total height
# a bottom-up traversal
while head < len(que): # queue is not empty
v = que[head]; head += 1 # pop que to v
total += h[v] # add to total
p = parent[v]
if p == 0: break
h[p] = max(h[p],h[v]+1)
deg[p] -= 1 # child leave
if deg[p] == 0: que.append(p)
#
# root must be the last one in the queue
print(que[-1])
print(total)
```
計算一下時間複雜度，輸入以及把找deg為0的點花了$O(n)$；while迴圈裡面只有$O(1)$的運算，問題是while迴圈做了幾次。因為每次有一點離開點queue，而一個點不可能進入queue兩次，所以整個時間複雜度是$O(n)$，比改善前好太多了。這個題目在APCS五級分的程度已經算難的，如果第一次看tree就看得懂，恭禧你，如果不太能了解，沒關係，後面還有專門的章節來講樹狀圖。
接下來要看個比較簡單的例子，這是堆疊運用的經典題目。
---
##### P-3-2. 括弧配對
在本題中我們假設有三種括弧：{ },( ),[ ]。輸入一個由括弧組成的字串，請判斷是否是平衡的，括弧可以巢狀但是不可以交叉，例如「()[]{[]}」、「[(()){}]」、「[(){}{}]{}()」都是平衡的，但「([)]」不是平衡的，此外「()\[」也不是，因為\[沒有配對。
Time limit: 1秒
輸入格式：輸入第一行是一個整數 $n$ 表示以下有 $n$ 行，每行是一個表示式，由六種括弧字元組成的字串，沒有其他字元，字串長度不超過150。
輸出：依序輸出每行是否是平衡的括弧，是則輸出yes，否則輸出no。
```
範例輸入：
5
()[]{[]}
[(()){}]
[(){}{}]{}()
([)]
()[
範例結果：
yes
yes
yes
no
no
```
---
括弧配對其實是計算表示式(expression evaluation)的其中一個環節，是資料結構課程中的一個重要課題，因為這是程式compiler裡面一定要做的工作。括弧的結構事實上也是遞迴定義的，所以可以用遞迴的方式做，但用堆疊更簡單。用堆疊檢查括弧是否平衡的算法也很直覺，基本上我們要找到每一個右括弧對應的左括弧，算法如下：
>啟用一個stack stk。掃描輸入字串的每一個字元，
如果是左括弧的一種：將他壓入stk；
否則(是右括弧)，取出堆疊最上方的左括弧與其配對，如果不配，則錯誤。
如果字串結束後堆疊中還有東西，也是錯誤。
如果都沒錯誤則是平衡的。
以下是直接實作這個算法的範例程式。我們寫一個函數 $balance(s)$ 來判斷字串 $s$ 是否是平衡的，第3行是初始化一個空的list當做stack，然後開始歷遍所有字元。左括弧就直接推入stack(第5 ~ 6行)，否則為右括弧，留意要先判斷stack是否為空(第8行)，否則將stack pop到$p$，然後判斷是否配對成功。最後，在歷遍結束後，要看看stack是否恰好為空。
主程式部分則是一行一行讀入，呼叫balance來判斷並輸出。時間複雜度$O(n)$，因為每個字元(每次迴圈)只需要花$O(1)$的時間。
```python=
# p3-2 parenthesis matching
def balance(s): # if string s is balance
stk = [] # initial stack
for ch in s:
if ch in "([{": # left
stk.append(ch)
else: # right
if len(stk) == 0: return False
p = stk.pop()
if ch == ')':
if p != '(': return False
elif ch == ']':
if p != '[': return False
elif ch == '}':
if p != '{': return False
# end if
#
return len(stk) == 0 # empty stack
#
n = int(input())
for i in range(n):
s = input()
if balance(s): print('yes')
else: print('no')
```
前面這支乘是的時間複雜度與正確性都沒問題，但以下我們介紹兩個簡單的小技巧，讓程式更簡潔漂亮。請看以下的範例程式。
本題有三種括弧，在實作時要避免很繁瑣的窮舉三種括弧，我們寫一個字串$pattern$，將6種括弧字元對應到整數0 ~ 5，先排左括弧再排右括弧，同類的一對的讓他們剛好差3，這樣可以簡單的檢查是否配對：第6行找出字元$ch$在$pattern$中的位置$curr$。然後$curr<3$當然就是左括弧，右括弧的話，兩者相差剛好3就是配對成功。
第二個小技巧是一開始第4行時我們在堆疊底部放了一個 $-1$，這是一個不會跟任何右括弧配段成功的數字，我們用它來省略堆疊為空的檢查。這樣的技巧稱為sentinel(哨兵)，因為在邊界放哨兵就可以不必擔心不小心越界，有的時候可以簡化我們的程式。留意到如果是正確的配對，最後堆疊中應該恰好剩下一個元素，就是那個哨兵(第14行)。
```python=
# p3-2 parenthesis matching
pattern = "([{)]}"
def balance(s): # if string s is balance
stk = [-1] # sentinel, ignore check empty
for ch in s:
curr = pattern.index(ch) # 0 ~ 5
if curr < 3: # left
stk.append(curr)
else: # right
p = stk.pop()
if curr-3 != p: # not match
return False
#
return len(stk) == 1 # only sentinel is left
#
n = int(input())
for i in range(n):
s = input()
if balance(s): print('yes')
else: print('no')
```
下一個習題，我們是一個簡化版的計算表示式，輸入一個數學運算式，請計算出他的值，計算式中的運算只有加減乘，運算的數字都只有一位正整數。
---
##### Q-3-3. 加減乘除
輸入一個只有加、減、乘法的計算式，請計算並輸出其結果。其中的數字皆為一位正整數。
Time limit: 1秒
輸入格式：輸入一行是一個計算式，長度不超過100。假設是一個正確的計算式。
輸出：輸出計算結果。
```
範例輸入：
5+2*3-6-7*2
範例結果：
-9
```
提示：因為加減乘都是左結合的二元運算，左結合是指連續兩個運算時先算左邊，例如$2-3-5=(2-3)-5$。現在需要考慮的只有先乘後加減。
一開始先將第一個數字放起來，接著從前往後掃描計算式，每次考慮兩個字元，第一個一定是個運算符號(op)第二個一定是個數字(num)。
如果op是個乘法，我們可以立刻將前面的運算結果與num做運算，因為沒有別的運算優先權高與乘法。
如果是加法或減法，我們暫時保留不計算，為了方便起見，如果op是減法，我們就保留 - num，如果op是加法，就保留num。如此，所有保留的數字最後全部加起來就是答案。
完整的expression evaluation可以在資料結構的課本上或是網路上查到，要考慮的因素很多，所以做法比較複雜。
註：Python可以用eval()函數直接得到結果，但建議讀者不要使用這個函數，而是要練習這個做法。
下面一題是堆疊運用的經典題。
---
##### P-3-4. 最接近的高人 (APCS201902, subtask)
對於一個人來說，只要比他高的人就是高人。有N個人排成一列，對於每一個人，要找出排在他前方離他最近的高人，排在之後的高人不算，假設任兩個相鄰的人的距離都是1，本題要計算每個人和他前方最近高人的距離之總和。如果這個人前方沒有高人(前方沒人比他高)，距離以他的位置計算(等價於假設最前方有個無窮高的高人)。
Time limit: 1 秒
輸入格式：第一行有一個正整數N，第二行有N個正整數依序代表每個人的身高，相鄰數字間以空白隔開。$N\le 2e5$，身高不超過1e7。
輸出：輸出每個人與前方最近高人的距離總和。
```
範例輸入：
8
8 6 3 3 1 5 8 1
範例結果：
18
```
---
為了方便起見，我們可以假設在最前方位置0的地方有個無限大的數字(sentinel)，這樣可以簡化減少邊界的檢查。最天真無邪又直接的方法就是：對每一個 $i$，從 $i-1$ 開始往前一一尋找，直到碰到比他大的數字或者前方已走投無路。但是這個方法太慢，算一下複雜度，在最壞的情形下，每個人都要看過前方的所有人，所以複雜度是$O(n^2)$。這一題$n$是2e5，一定是$O(n)$或$O(n\log(n))$的方法。
要改善複雜度，要想想是否有沒有用的計算或資料。假設身高資料放在陣列 $a[]$，如果 $a[i-1] \le a[i]$，那麼 $a[i-1]$不可能是$i$之後的人的高人，因為由後往前找的時候會先碰到 $a[i]$，如果 $a[i]$ 不夠高，$a[i-1]$ 也一定不夠高。
同樣的道理，當我們計算到 $i$ 的時候，任何$j<i$ 且 $a[j] \le a[i]$ 的 $a[j]$ 都是沒有用的。如果我們丟掉那些沒有用的，會剩下甚麼呢？
**一個遞減的序列**。
只要維護好這個遞減序列，就可以提高計算效率。單調序列要用二分搜嗎？其實連二分搜都不需要，想想看，當處理 $a[i]$ 時，我們要先把單調序列後方不大於 $a[i]$ 的成員全部去除，然後最後一個就是 $a[i]$ 要找的高人，因為既然要做去除的動作，就一個一個比較就好了。
那麼，要如何維護這個單調序列呢？第一個想法可能是將那些沒用的刪除，那可不行，陣列禁不起的折騰就是插入與刪除，因為必須搬動其後的所有資料。想想我們要做的動作：每次會從序列後方刪除一些東西，在加入一個東西。答案呼之欲出了，因為只從後方加入與刪除，堆疊是最適合的。請看以下的範例程式，這個程式非常簡單。
身高資料放在 $a[i]$，讀入之後就不再變動。準備一個堆疊$S$放置那個單調序列在 $a[]$ 中的索引位置。對每一個 $a[i]$，從堆疊中pop掉所有不大於它的東西，然後堆疊的最上方就是 $i$ 的高人，接著把 $a[i]$ push進堆疊。
```python=
# p_3_4a, stack for index
n = int(input())
a = [10**7+1]+[int(x) for x in input().split()]
S = [0] # stack of indexes of monotonic seq
total = 0 # total distance
for i in range(1,n+1):
while a[S[-1]] <= a[i]: # pop until > a[i]
S.pop()
total += i - S[-1]
S.append(i)
#
print(total)
```
時間複雜度？看到雙迴圈以為是$O(n^2)$嗎？跑跑看就知道這麼快一定不是$O(n^2)$，難不成測資出太弱了！台語說：事情不像憨人想的那麼簡單。這個程式雖然有個雙迴圈，內層while迴圈也的確有可能某幾次跑到$O(n)$，但是整體的複雜度其實只有$O(n)$，原因是，雖然單一次while迴圈可能跑很多個pop，但是全體算起來不會pop超過 $n$ 次，因為每個傢伙只會進入堆疊一次，進去一次不可能出來兩次，所以整體的複雜度是$O(n)$。這種算總帳的方式來計算複雜度稱為均攤分析(amortized analysis)，這個題目是均攤分析的經典教學題目。
上面的範例程式把資料放在 $a[]$，用stack存index，事實上我們也可以只存那個單調序列，這樣在stack中要存身高與位置，以下是這樣的寫法，這只是給有興趣的人參考，上面那個寫法就夠好了。
```python=
# p_3_4b, stack for index and height
n = int(input())
S = [(10**7+1,-1)] # monotonic stack of (height,idx)
# initial is sentinel with idx=-1
total = 0 # total distance
for i,h in enumerate([int(x) for x in input().split()]):
while S[-1][0] <= h: # pop until > a[i]
S.pop()
total += i - S[-1][1]
S.append((h,i))
#
print(total)
```
下面這一題，是前一題的一種變化，我們當作習題。
---
##### Q-3-5. 帶著板凳排雞排的高人 (APCS201902)
身高高不一定比較厲害，個子矮的如果帶板凳可能會變高。有 $n$ 個人排隊買雞排，由前往後從1到 $n$ 編號，編號 $i$ 的身高為 $h(i)$ 而他帶的板凳高度為 $p(i)$。若 $j$ 在 $i$ 之前且 $j$ 的身高大於 $i$ 站在自己板凳上的高度，也就是說 $h(j)>h(i)+p(i)$，則 $j$ 是 $i$ 的「無法超越的位置」，若 $j$ 是 $i$ 最後的無法超越位置，則兩人之間的人數 $(i-j-1)$ 稱為 $i$ 的「最大可挑戰人數」$S(i)$；如果 $i$ 沒有無法超越位置，則最大可挑戰人數 $S(i)=i-1$，也就是排在他之前全部的人數。
舉例來說，假設$n=5$，身高$h$依序為$(5, 4, 1, 1, 3)$而板凳高度$p$依序是 $(0, 0, 4, 0, 1)$。計算可得$h(i)+p(i)=(5, 4, 5, 1,4)$，編號1的人前面沒有人，所以1的最大可挑戰人數$S(1) = 0$。對編號2的人而言，$h(2)+p(2)= 4$，而往前看到第一個大於4的是$h(1)=5$，所以$S(2)=2-1-1=0$。而$h(3)+p(3) =5$，前面沒有人的身高大於5，所以$S(3)=2$。而$h(4)+p(4)=1$， $h(2) = 4 > 1$，所以位置2是4的無法超越位置，$S(4)=4-2-1=1$。同理可求出$S(5)=3$，他的不可超越位置是1的身高5。
輸入$h()$與$p()$，請計算所有人$S(i)$的總和。
Time limit: 3秒
輸入格式：第一行為$n$，$n \le 2e5$；第二行有$n$ 個正整數，依序是身高$h()$；第三行有$n$個非負整數，依序代表是$p()$；數值都不超過1e7，同一行數字之間都是以空白間隔。
輸出：輸出$S(i)$的總和。
```
範例輸入：
5
5 4 1 1 3
0 0 4 0 1
範例結果：
6
```
Q-3-5提示：本題與P-3-4的主要差異是多了板凳高度，另外有個小差異是計算的值略有不同。例題的題解中最重要的重點是我們只要維護一個單調遞減序列，既然是單調序列，就可以用二分搜找到第 $i$ 個人站在板凳上的高度。
雖然保護樹木很重要，尤其學資料結構與演算法的人，對樹總是抱持著尊敬的心，但是有些樹種的目的就是要砍下來當木材的，請環保人士不要對下一題的名字抗議。來看下一個例題，砍樹。
---
##### P-3-6. 砍樹 (APCS202001)
N棵樹種在一排，現階段砍樹必須符合以下的條件：「讓它向左或向右倒下，倒下時不會超過林場的左右範圍 $[0,L]$ 之外，也不會壓到其它尚未砍除的樹木。」。你的工作就是計算能砍除的樹木。
若 $c[i]$ 代表第 $i$ 棵樹的位置座標，$h[i]$ 代表高度。向左倒下壓到的範圍為 $[c[i]-h[i],c[i]]$，而向右倒下壓到的範圍為 $[c[i],c[i]+h[i]]$。如果倒下的範圍內有其它尚未砍除的樹就稱為壓到，剛好在端點不算壓到。
我們可以不斷找到滿足砍除條件的樹木，將它砍倒後移除，然後再去找下一棵可以砍除的樹木，直到沒有樹木可以砍為止。無論砍樹的順序為何，最後能砍除的樹木是相同的。
Time limit: 1秒
輸入格式：第一行為正整數$N$以及一個正整數$L$，代表樹的數量與右邊界的座標；第二行有$N$個正整數代表這$N$棵樹的座標，座標是從小到大排序的；第三行有$N$個正整數代表樹的高度。同一行數字之間以空白間隔，$N\le 1e5$，$L$與樹高都不超過1e9。
輸出：第一行輸出能被砍除之樹木數量，第二行輸出能被砍除之樹木中最高的高度。
```
範例輸入：
6 140
10 30 50 70 100 125
30 15 55 10 55 25
範例結果：
4
30
```
題目中有句話：無論砍樹的順序為何，最後能砍除的樹木是相同的。所以不斷找到滿足砍除條件的樹木，將它砍倒後移除，直到沒有樹木可以砍為止，就可以得到正確的答案，問題只是效率好不好。我們先看看天真的作法。
寫程式最重要的是知道每次要做甚麼事情，資料中存放的是甚麼，有何特性。如果我們用陣列來存這些樹，那麼立刻碰到一個問題：當樹被砍掉了之後怎麼辦？我們當然必須維護好陣列中是沒有被砍掉的樹，否則判斷就會出問題。第一個想法就是想要把砍倒的樹的資料從陣列中移除，那麼陣列中如何移除資料呢？陣列最經不起插入與刪除的折騰，在Python雖然提供list.pop(idx)來刪除list中第idx個元素的指令，但是這樣做不只效率不佳也可能犯錯。
我們先看一個簡單的例子。假設我們要在一個整數list中刪除所有奇數，有人可能會這樣寫：
```python=
a = [2,1,1,4,5]
for i in range(len(a)):
if a[i]%2: a.pop(i)
```
如果把這個程式執行看看，會發現引發list index out of range的錯誤，而且也沒有把所有奇數刪除。原因是我們在歷遍的過程中刪除容器內元素，當你刪除$a[1]$時，後面的元素往前移動，與原先的index不同。
如果小心的想想，可以發現在這個例子中如果刪除的動作由後往前，則可以避免這樣的錯誤。但是如果是不同的狀況，還是可能引發錯誤，基本上，**在歷遍的過程中增刪或變動容器的內容是一個危險的動作**，必須留意是否會有副作用。一般來說，一個比較好的做法是把要留下來的元素放到另外一個list中蒐集起來，到迴圈末尾再還給原來的list。以上面的例子來說，可以這樣寫。
```python=
a = [2,1,1,4,5]
tem = []
for i in range(len(a)):
if a[i]%2 == 0 : tem.append(a[i])
a = tem
```
回到我們砍樹的問題。下面的範例程式是每次刪除可以砍的樹，直到沒有樹可以砍為止。刪除時，我們將存活的樹蒐集到一個tem中。這裡我們加了一個小技巧，在兩個邊界放上兩個不會檢查的樹(sentinel)，這樣可以讓第一棵與最後一棵的檢查方式與其他都一樣，否則頭尾的條件要另外寫。
```python=
n, l = map(int, input().split())
c = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
alive = [[0,0]]+ [[c[i],h[i]] for i in range(n)] +[[l,0]]
# first and last is sentinel
total = high =0 # answer
while True: # until no change
temp = [[0,0]] # sentinel
for i in range(1,len(alive)-1) : # ignore sentinel
if alive[i][0]-alive[i][1] >= alive[i-1][0] \
or alive[i][0]+alive[i][1] <= alive[i+1][0] :
# removable
total += 1; high = max(high, alive[i][1])
else:
temp.append(alive[i])
# end if
temp.append([l,0]) # sentinel
if len(temp) == len(alive): break # no change
alive = temp
#end for
print(total); print(high)
```
複雜度如何？$O(n^2)$，因為每一回合可能只有砍很少的樹，甚至只砍一棵樹，那麼就可能需要$O(n)$個回合，每個回合花$O(n)$的時間。
處理陣列資料被移除的方式除了真的把他移除之外，還有一種常用的方法是將他標記，這一題我們可以把砍除的樹標記為高度0，而不必把它刪除，但是有一好沒兩好，我們在檢查左右存活的樹的時候，就必須往左往右尋找到第一棵還存活的樹，因為旁邊的樹可能已經被砍除。以下是這樣寫出來的程式，很不幸，複雜度還是$O(n^2)$。
```python=
# P-3-6, O(n^2) slow method, mark removed tree
n, l = map(int, input().split())
c = [0]+[int(x) for x in input().split()]+[l]
h = [1]+[int(x) for x in input().split()]+[1]
# first and last is sentinel any h>0, h=0 is removed
total = high =0 # answer
modify = True
while modify: # repeat until no tree can be removed
modify = False # if modified
for i in range(1,n+1): # check each tree
if h[i]==0: continue # already removed
prev, inext = i-1, i+1
while h[prev]==0: prev -= 1 # previous remaining tree
while h[inext]==0: inext += 1 # next remaining tree
if c[i]-h[i]>=c[prev] or c[i]+h[i]<=c[inext]:
total += 1
high = max(high,h[i])
h[i] = 0 # remove
modify = True
#
#
print(total); print(high)
```
這一題有人以為應該從矮的樹開始砍，但這顯然沒有甚麼幫助，因為高的樹可能比矮的樹先砍除。其實我們只要想想：目前不能被砍除的樹，什麼狀況會變成可以砍除呢？一定與他相鄰的(還存活的)樹被砍掉，才有可能空出多餘的空間。加油！解法就快要浮現了。
假設我們以一個佇列Q存放那些砍除的樹，一開始先檢查一次那些樹可以被砍除，把他們放入Q，然後我們一次將Q中的樹拿出來，檢查他左右相鄰的樹是否可以變成可以砍除，如果可以，就砍除並放入Q，這樣做直到Q中沒有樹為止。
因為每一棵被砍除的樹都有考慮他的左右，所以不會漏砍。這是個正確的算法，但是這個過程中牽涉一個問題，就是必須很快的決定某棵樹的左右鄰居。趁這個機會我們簡單介紹一下串列鏈結(linked list)。
### 鏈結串列(Linked list)
串列是一個很重要的資料結構，顧名思義，他是將資料以鏈結的方式串成一列。他最重要的運用場合是當資料無法依序儲存在連續空間的時候，否則，用陣列會比串列更簡單有效率。但是陣列的缺點就是必須連續擺放，在某些應用時，這個限制變得不可能，例如檔案存在硬碟中，因為檔案會新增與刪除，所以將一個檔案放在連續的磁碟位置變得不可能。鏈結串列的概念是不必把資料連續擺放，只要對每一筆資料記載他的下一筆所在位置，有了這些資料，我們就可以一筆接一筆的把全部的資料追蹤一遍了。鏈結串列有單向與雙向，看應用而定，雙向的串列我們會儲存每一個資料的前一筆與下一筆鏈結，單向的只存下一筆。
通常鏈結串列在運用時多半搭配記憶體的配置，在Python來說就是以物件的方式來產生新的節點。但是在解題程式中，我們通常會避免這個做法(但不是不可以)，原因之一是除錯較麻煩，另外一個原因是解題的程式通常都有辦法用偷懶的方式來做，因為不必考慮記憶體配置與回收。這份教材是針對考試與競賽的解題，所以我們就不對這個部份多做說明了，有興趣的讀者可以很容易在網路上或者資料結構的教科書中找到教學文件。
在解題的場合，我們可以在陣列中構造所需的鏈結串列，用陣列的索引(index)來取代記憶體位置(指標)。我們接著就看看串列如何用在P-3-6。
在下面的範例程式中，我們一樣在最前面與最後面加上哨兵，真正的資料是編號 1 ~ $n$。對每一棵樹除了原來的中心位置與高度之外，我們建立以下資料：
* $prev[i]$：前一棵樹的index，初始 $prev[i]=i-1$。
* $inext[i]$：下一棵樹的index，初始 $inext[i]=i+1$。
* $alive[i]$：第 $i$ 棵樹是否還存活。
我們以一個queue $que$存放那些已知可以砍但尚未砍的樹，保持不變性：$alive[i]=False$ 若且惟若 $i$ 已經進入 $que$。這個的作用是避免一棵樹被多次重複放入 $que$ 中。
程式一開始先做一次地毯式搜索，第13 ~ 16行檢查每一棵樹是否可以移除，若是，則加入 $que$並且更改 $alive$ 值。接著進入一個while迴圈，迴圈每次將 $que$ 中的一棵樹砍除，迴圈會一直做到 $que$ 變空的為止。
砍除一棵樹要做的是更新答案(第21 ~ 22行)，然後把它從鏈結串列中移除，串列中移除不需要像陣列一樣搬動其他資料，只需要將左邊的 $inext$ 改成 $i$ 的 $inext$，把右邊的 $prev$ 改成 $i$ 的 $prev$，這樣在串列中沿著鏈結追蹤時就再也找不到 $i$ 了，也就相當於從串列中移除了 (第24 ~ 25行)。
最後，第27 ~ 32行我們檢查在 $i$ 砍除之後，前一棵樹與下一棵樹是否變成可以移除。
對於複雜度來說，初始化的動作在$O(n)$內完成，while迴圈內的動作都是$O(1)$，而每棵樹最多只會進入queue中一次，所以整體的複雜度是O(n)。
```python=
# P_3_6b, topological sort and linked list
n, l = map(int, input().split())
c = [0]+[int(x) for x in input().split()]+[l]
h = [l+1]+[int(x) for x in input().split()]+[l+1]
# first and last is sentinel with height oo
prev = [0]+list(range(n+1)) # previous alive
inext = [1]+list(range(2,n+2))+[n+1] # next alive
alive = [False]+[True]*n+[False] # if alive
total = high =0 # answer
que = [] # queue of index of removable tree
head = 0 # head of queue
# initial removable
for i in range(1,n+1):
if c[i]-h[i] >= c[i-1] or c[i]+h[i]<=c[i+1]:
que.append(i)
alive[i] = False
# remove tree in que
while head < len(que): # until empty
i = que[head]; head += 1 # pop from que
# remove i
total += 1 # update answer
high = max(high, h[i])
# remove from linked list
inext[prev[i]] = inext[i]
prev[inext[i]] = prev[i]
# check if prev and inext are removale
if alive[prev[i]] and c[prev[i]]+h[prev[i]] <= c[inext[i]]:
que.append(prev[i])
alive[prev[i]] = False
if alive[inext[i]] and c[inext[i]]-h[inext[i]] >= c[prev[i]]:
que.append(inext[i])
alive[inext[i]] = False
#
print(total,high, sep='\n')
```
上面這個程式的方法，其實類似於圖論演算法中計算dag的topological sort所用的方式，我們在後續介紹圖的章節中會再介紹。
有個笑話說：聽演算法老師講解題目解法時，就跟看名偵探柯南一樣，前面80%都可以忽略，只聽後面20%就可以了，因為他們總是先講一些很爛或很複雜的方法，最後才告訴你一個既有效率又簡潔的方法。
這笑話其實是有它的真實性的，在教學上，我們往往先從直覺的方法開始，然後循著某些思考模式，找到更好更漂亮的方法。事實上，在演算法學者的研究過程中往往也是如此。
砍樹這一題，我們先講了直覺地從陣列中移除的方法，時間複雜度$O(n^2)$，然後，講了以做記號代替移除的方法，時間複雜度還是$O(n^2)$。然後用linked list來克服需要左右找存活的樹的問題，改善時間複雜度到$O(n)$。事實上，這一題還有更簡單的作法。
回到剛才講到的關鍵點：**一棵目前不能被砍除的樹，只有在相鄰的樹被砍掉後才有可能變成可以砍除**。假設我們從前往後掃描所有的樹，可以砍的就砍了，不能砍的暫且保留起來，那麼被保留的樹和時會變成可以被砍呢？因為他的左方(前方)不會變動(我們從左往右做)，所以一定是右邊的樹被砍了之後才有可能。此外，那些被保留的樹，一定只有最後一棵需要考慮！因為其他的被保留樹的右邊都沒有動。
好了，最後的問題是要怎麼存那些被保留的樹呢？我們一樣可以用鏈結串列，但是沒有必要，因為我們只要知道每一棵樹還存活的的前一棵樹就可以，而且重點是我們只需要檢查最後一棵保留樹，也只需要從後面往前刪除。
答案出來了，**用堆疊就夠了**。
以下是用堆疊寫的範例程式。需要留意的是，當一棵樹被砍除時，我們要用一個while迴圈對堆疊出口的樹做檢查，因為可能砍到一棵可能引發連鎖效應一路往前砍掉很多棵。複雜度$O(n)$，因為每個樹最多只進入堆疊一次。請注意我們在堆疊中只放樹的index，當然也可以寫成在堆疊中存放樹的位置與高度。
```python=
# P-3-6, O(n) using stack
n, l = map(int, input().split())
c = [0] + [int(x) for x in input().split()]+[l]
h = [1000000001]+[int(x) for x in input().split()]+[1000000001]
# first and last are sentinel
stack = [0] # previous reserved tree
total = high =0
for i in range(1, n+1):
if c[i]-h[i]>=c[stack[-1]] or c[i]+h[i]<=c[i+1] :
# removable
total += 1; high = max(high, h[i])
# check top of stack
while c[stack[-1]]+h[stack[-1]]<=c[i+1] :
idx = stack.pop() # remove
total +=1; high = max(high, h[idx])
#end while
else: # reserved
stack.append(i)
# end if
#end for
print(total); print(high)
```
### 滑動視窗(Sliding window)
接下來要介紹滑動視窗的技巧，這個名字可能不是很統一，基本上是以兩個指標維護一段區間，然後逐步將這區間從前往後(從左往右)移動。維護兩個指標這一類的方法也有人稱為雙指標法，但也包含兩個指標從兩端往中間移動，就像我們曾在介紹過，在排好序的序列中尋找兩數相加之和的問題時，可以用兩個指標逐步移動來做，會比連續的二分搜還好。也有人稱為爬行法，維護一個逐步右移的區段很像是毛毛蟲的爬行，前方先往前，後方再跟上，不斷的重複這個亦步亦趨的方式。反正名稱不重要，我們來看看一些例子。
下一個例題與P-2-11幾乎相同，但此處限制輸入的數字為正整數，原題正負不限，所以這一題比較簡單。原題超過APCS考試範圍，這一題則是滑動視窗的基本題型。
---
##### P-3-7. 正整數序列之最接近的區間和
輸入一個正整數序列$A[1], A[2], …, A[n]$，另外給了一個非負整數$K$，請計算哪些連續區段的和最接近$K$而不超過$K$，以及這樣的區間有幾個。$n$不超過20萬，輸入數字與K皆不超過10億。
Time limit: 1秒
輸入格式：第一行是$n$與$K$，第二行$n$個整數是$A[i]$，同行數字以空白間隔。
輸出格式：第一行輸出最接近$K$但不超過$K$的和，第二行輸出這樣的區間有幾個。
```
範例輸入：
5 10
4 3 1 7 4
範例輸出：
8
2
說明：(4,3,1)與(1,7)兩個區間的和都是8。
```
---
我們的目標對於所有可能的右端$right$，找出最佳的左端$left$，滿足$\sum_{i=left}^{right}A[i] < K$，最佳的意思是總和越大越好，因為都是正整數，所以也就是找出最小的$left$。
我們從$right=0$開始，將$right$逐步往右推，每次右端移動後，調整左端維護迴圈不變性：在$[left,right]$閉區間的總和不超過$K$。
因為都是正數，所以當$right$增加時，他對應的最佳左端不可能往左。證明：若$[left-1,right+1]$的區間和不超過$K$，則$[left-1,right]$的區間和也不超過$K$，所以$left$不可能是$right$對應的最佳左端。
因為要找最小左端，所以我們要移動左端直到滿足區段和不超過$K$為止。每次右端移動一格，就會找到以此為右端的最佳解，所以當視窗向右滑到底時，我們就找出了最佳解。
範例程式如下。雖然有雙迴圈，在外迴圈一次中，內迴圈可能執行多次，但因為雙指針皆一路右移，從不回頭，所以以均攤分析來說，總時間複雜度是$O(n)$。
```python=
# P3-7, sum of subarray, positive
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
best = n_best = 0 #
isum = 0 # sum(a[left:right+1)
left = 0
# move right one by one
for right in range(n):
isum += a[right]
# move left until sum<=k
while isum > k:
isum -= a[left]
left += 1
# check answer
if isum > best:
best = isum
n_best = 1
elif isum == best: n_best += 1
#
print(best); print(n_best)
```
上面一題的視窗大小是會變動的，其實比較像毛毛蟲，不像窗戶。下面一題我們來個固定長度的窗戶。
---
##### P-3-8. 固定長度區間的最大區段差
對於序列的一個連續區段來說，區段差是指區段內的最大值減去區段內的最小值。有$N$個非負整數組成的序列$seq$，請計算在所有長度為$L$的連續區段中，最大的區段差為何。
Time limit: 1秒
輸入格式：第一行是$N$與$L$，第二行是序列內容，相鄰數字間以空白隔開。$L \le N \le 2e5$，數字不超過1e9。
輸出：輸出所求的最大區間差。
範例輸入：
9 4
1 4 3 6 9 8 5 7 1
範例結果：
7
說明：(8,5,7,1)的長度是4，區段差是7。
---
連續的$L$個格子是一個窗戶，長度$N$的序列有$N-L+1$個可能的窗戶位置，對每一個位置，把窗戶內的最大值減去最小值，可以得到這個區段的區段差，所有$N-L+1$個區段差中要找到最大的。直接的天真做法如下：
```python=
# P3-8, n^2 slow
n, l = map(int, input().split())
a = [int(x) for x in input().split()]
dmax = 0 # max difference
for i in range(n-l+1): # each possible left
t = max(a[i:i+l]) - min(a[i:i+l])
dmax = max(dmax,t)
print(dmax)
```
天真的做法當然不行，每個區段跑一遍找最大最小需要$O(L)$，$N-L+1$個區段就是$O(L(N-L+1))$，$L=N/2$時，就是$O(N^2)$。
這個題目解法的主要想法是紀錄區段內的最大值與最小值，當區段往右移動時，更新最大與最小值。乍看之下，更新最大最小值很容易就可以做到，因為只移進來一個值，移出去一個值。可是仔細想想，如果移出去的是最大值，那最大值會變成多少呢？可能會變也可能不變，這麼想下去覺得問題沒有那麼簡單。
這裡要介紹的是「單調隊列」解法，我們先看最大值的找法，最小值的做法完全類似。目標是在一個陣列中找出所有長度為$L$的子陣列的最大值。
### 單調隊列
單調隊列背後的道理可以以下面情境來打個比方。
「學生一屆一屆的進入學校，小明很喜歡程式比賽，當他進入學校時，如果有學長姐厲害到小明難以超越，那沒關係，小明在學校還是有出頭之日，因為學長姐會比他先畢業。但如果在小明之後新進來一位他無法超越的學弟妹，那完蛋了，小明在該校沒有什麼機會獨領風騷了，因為他會先畢業。」
我們維護一個長度$L$的視窗在序列一步一步右移，可以看成一屆有一位學生進入，視窗長度固定為$L$，也就是學生進入後$L$屆就會畢業，同時在校的也恰有$L$位，我們要找出每一年最厲害的校內冠軍。
上面的例子告訴我們，對於某個 $i$ (小明)，如果同時在視窗內有個 $j$，$seq[j]>seq[i]$，如果$j<i$，($j$是學長姐)，則 $i$ 尚未絕望，將來還有可能有機會當冠軍；但如果 $j>i$，則 $i$ 從此刻起永遠不會是校內冠軍了。
如果我們把視窗內這些不可能成為冠軍的去除不看，那麼視窗內的將是個單調下降的子序列(monotonically decreasing subsequene)。這就是**單調隊列**。
我們用一個容器存放目前的隊列，維護的迴圈不變性是：
1. 隊列是遞減的
2. 隊列中均為尚在範圍內的元素
請注意，**根據迴圈不變性，隊列最前方的就是區間最大值**。每次新元素進入時，我們做兩件事：
1. 新生刪除所有不比自己強的學長姐。根據迴圈不變性，隊列為遞減的，我們只要從後往前刪除比新元素小的成員，當碰到第一個大於他的元素，刪除動作即已完成，因為前面的更大。刪除完成後再將自己加入隊列尾端(新生永遠有希望)。
2. 檢查最前方，也就是最大的元素是否已經出界，若是，將其移除。
要使用什麼容器來存放隊列呢？因為要支援前方與後方的移除，典型的做法是用deque (double ended queue雙向佇列)。Python也有提供deque，我個人比較喜歡用list加上一個head變數記錄頭端的位置即可。因為list尾端的刪除與新增都是$O(1)$，所以很方便。
其實這一題跟例題「P-3-4最接近的高人」有點像，都是維護一個單調隊列，但P-3-4的左端不會離開，是個monotonic stack，本題資料有可能從窗戶左端離開。
找最小值的做法相同，只要改變大小關係就可以了，以下是範例程式。我們用兩個deque：max_q與min_q，因為要紀錄數值與位置，每一個deque的成員用一個(value,index)的tuple，當然也可以只存index，再到序列中查值。
第8行開始歷遍所有序列元素($seq[i]=p$)，維護max_q時，先從尾端刪除所有不大於 $p$ 的成員函數，然後將 $p$ 放入尾端，最後檢查頭端是否已經出界，出界時我們只要把headmax加一就可以了，不必真的刪除。處理完畢後max_q[headmax]就是窗戶內的最大值。最小值的做法完全類似。
時間複雜度是$O(n)$，因為每個成員最多只會進入大小隊列各一次，所以用均攤分析，內迴圈的總執行次數是$O(n)$。
```python=
# P3-8, monotonic deque O(n)
n, l = map(int, input().split())
seq = [int(x) for x in input().split()]
dmax = 0 # max difference
max_q, headmax = [], 0 # max deque decreasing seq
min_q, headmin = [], 0 # min deque increasing seq
# deque: (value,idx)
for i,v in enumerate(seq): # each (index,value)
# maintain max_q
while headmax<len(max_q) and max_q[-1][0]<=v:
max_q.pop() # pop smaller
max_q.append((v,i))
if max_q[headmax][1] <= i-l: # out of date
headmax += 1
# range max is at max_q[headmax]
# maintain min_q
while headmin<len(min_q) and min_q[-1][0]>=v:
min_q.pop() # pop smaller
min_q.append((v,i))
if min_q[headmin][1] <= i-l: # out of date
headmin += 1
# range min is at min_q[headmin]
# check answer
dmax = max(dmax,max_q[headmax][0]-min_q[headmin][0])
#
print(dmax)
```
我們也展示一下使用python物件deque()的寫法，這裡我們deque中只放index，留意需要import。
```python=
# P3-8, monotonic deque O(n)
from collections import deque
n, l = map(int, input().split())
seq = [int(x) for x in input().split()]
dmax = 0 # max difference
max_q = deque() # max deque decreasing seq
min_q = deque() # min deque increasing seq
# element in deque is index
for i,v in enumerate(seq): # each (index,value)
# maintain max_q
while len(max_q) and seq[max_q[-1]]<=v:
max_q.pop() # pop smaller
max_q.append(i)
if max_q[0] <= i-l: # out of date
max_q.popleft()
# range max is at max_q[0]
# maintain min_q
while len(min_q) and seq[min_q[-1]]>=v:
min_q.pop() # pop smaller
min_q.append(i)
if min_q[0] <= i-l: # out of date
min_q.popleft()
# range min is at min_q[headmin]
# check answer
dmax = max(dmax,seq[max_q[0]]-seq[min_q[0]])
#
print(dmax)
```
前面的題目都是跟序列中數字的大小有關係，接下來看有數字但沒有大小的題目，一共有四個類似的題目，我們示範兩題，另外兩題當做習題。
---
##### P-3-9. 最多色彩帶
有一條細長的彩帶，彩帶區分成 $n$ 格，每一格的長度都是1，每一格都有一個顏色，相鄰可能同色。給定長度限制$L$，請找出此彩帶長度$L$的連續區段最多可能有多少種顏色。
Time limit: 2秒
輸入格式：第一行是兩個正整數 $n$ 和 $L$，滿足 $2 \le L \le n \le 2e5$；第二行有 $n$ 個以空白間隔的數字，依序代表彩帶從左到右每一格的顏色編號，顏色編號為小於 $n$ 的非負整數。
輸出：長度$L$的彩帶區段最多有多少種顏色。
範例輸入：
10 5
4 6 1 4 0 6 8 0 5 6
範例結果：
5
說明：區間 [3, 7] 有5色。
---
這是一個簡單的題目，把一個固定長度$L$的視窗，從左到右逐步滑動過去，找出視窗內的顏色總數就行了。所以重點只有一個：如何找出是窗內的顏色數。因為顏色是從0開始連續編號，我們只要準備一個表格cnt，以 cnt[i] 紀錄顏色 i 的出現次數。每次進入一個顏色，就將該顏色計數器加一；移出一個顏色就將顏色計數器減一。那怎麼知道窗內的顏色數呢？不能每次都掃描表格，因為太浪費時間，我們可以只關注顏色數的變動。我們可以用一個變數記錄目前的顏色數，若cnt[i]+1之後變成1，那就知道顏色數多了一種；相同的，如果cnt[i]減1之後變成0就是少了一色，其他狀況的顏色數量沒變化。
以下是範例程式，時間複雜度$O(n)$。
```python=
# P_3_9, sliding window, max color of fixed length
n, l = map(int, input().split())
seq = [int(x) for x in input().split()]
cnt = [0]*n # number of color i
# initial window
n_color = 0 # number of distinct color
for i,color in enumerate(seq[:l]):
cnt[color] += 1
if cnt[color] == 1: n_color += 1
maxc = 0 # max number of color
# sliding window, [left, right]
# color = seq[i], left = i-l
for left,color in enumerate(seq[l:]):
cnt[color] += 1
if cnt[color] == 1: n_color += 1
lcolor = seq[left]
cnt[lcolor] -= 1
if cnt[lcolor] == 0: n_color -= 1
maxc = max(maxc, n_color)
#
print(maxc)
```
下面一題很類似，但多了一些要處理的問題。
##### P-3-10. 全彩彩帶 (需離散化或字典) (@@)
有一條細長的彩帶，彩帶區分成$n$格，每一格的長度都是1，每一格都有一個顏色，相鄰可能同色。如果一段彩帶中的顏色包含整段彩帶的所有顏色，則稱為「全彩彩帶」。請計算出最短的全彩彩帶長度。
Time limit: 4秒
輸入格式：第一行為整數$n$，第二行有 $n$ 個以空白間隔的非負整數，依序代表彩帶從左到右每一格的顏色編號，$n \le 2e5$，顏色編號不超過1e9。
輸出：最短的全彩彩帶長度。
範例輸入：
10
6 4 1 6 0 4 5 0 7 4
範例結果：
7
說明：彩帶共有{0,1,4,5,6,7}六色區，區間[3, 9]是最短的包含六色區段。
---
基本上我們打算維持住一個視窗，視窗裡面包含所有的色彩，每次當視窗往右堆一格的時候，檢查左端是否可以往右移以便縮減寬度，當視窗推到底之後，我們就已經檢查過所有可能的右端點，在過程中找到最窄的視窗寬度，就是答案。
何時左端可以縮減呢？答案很明顯，如果左端點顏色在是窗內出現超過一次，就可以丟棄，否則，不能右移。另外一個問題是顏色的編號範圍，在前一題P-3-9時，顏色的編號不大於$n$，所以我們可以很容易的開一個表格當每個顏色的計數器，但是在這一題，顏色的編號可能達到10億，想要開一個10億的表格是會碰上麻煩的。
雖然編號可能高達10億，但是資料最多就只有20萬個，顏色當然最多也只有20萬種，因此，如果我們可以將顏色的編號先修改為0開始的連續編號，就可以用上一題的表格方式來處理計數器了。在第二章的P-2-2中我們示範了如何離散化(coordinate compression座標壓縮)，在這裡就可以派上用場了。
下面的範例程式是以sort以及自己寫二分搜來做離散化的寫法，副程式c_id()就是自己寫的二分搜來查詢color在dic[]中的位置，這個副程式也可以簡單以第13行註解掉的bisect_left來做。
在第21行我們把所有的seq[]都換成rank之後就完成了離散化的工作。接著進行滑動視窗來找答案。以兩個變數left與right來維持至目前的視窗範圍，right每次加1，left則只要顏色還有重複就盡可能縮減。要注意的是，為了簡化程式碼，我們並不保證一開始的視窗是包含所有的色彩的，但是在第34行加了一個 if 來確保當全部的色彩都在時，才會記錄答案。如果一開始要先找到出於全彩視窗也可以，但可能要多寫幾行。這個範例的程式碼雖然有一點長(其實也不算太長)，但是方法的正確性不難理解，重點在於左端的顏色如果在是窗內僅出現一次，那就絕對不能右移。
時間複雜度$O(n\log n)$，其中離散化花了$O(n\log n)$的時間，sliding window只花$O(n)$。
```python=
# P_3_10 shortest all-color range, only basic instruction
import bisect
n = int(input())
seq = [int(x) for x in input().split()]
# sort all distinct into dic
v = sorted(seq)
dic = [v[0]]
for p in v[1:]:
if p != dic[-1]: # distinct
dic.append(p)
# binary search to find dic[idx]= color
def c_id(color):
#return bisect.bisect_left(dic,color)
l,r = 0,len(dic) # range = [l,r)
while r>l+1:
mid = (l+r)>>1
if color == dic[mid]: return mid
elif color < dic[mid]:
r = mid
else: l = mid
return l
# replace color with its rank
seq = [c_id(c) for c in seq]
# end of discretization, start sliding window
shortest = n # initial answer
n_color = 0 #num of color in window [left, right]
left = 0
cnt = [0]*len(dic) # len(dic) is number of color
for right,color in enumerate(seq):
cnt[color] += 1
if cnt[color] == 1: n_color += 1
# shrink left until left color appear only once
while cnt[seq[left]] > 1:
cnt[seq[left]] -= 1
left += 1
if n_color == len(dic): # all color in window
shortest = min(shortest, right-left+1)
#
print(shortest)
```
在第二章我們曾經揭露出以set/dict來做離散化的寫法，這一題因為顏色之間其實並沒有大小關係，所以用字典做就更加簡單了，以下我們展示用dict來做的範例程式。這裡再強調一次，以APCS來說，應該不至於會考出非用特殊資料結構(set/dict)才能解的題目，但是很多題目如果使用這些資料結構可以簡化我們的程式，在考試與比賽時，程式碼的長短對犯錯機率與debug影響很大，所以要不要學，要看個人狀況而定，程度已經夠了，就多學一點好用的工具，如果對基本的程式還很生疏，就練習熟練後再說。
註：集合與字典對C/C\++來說可能算特殊資料結構，但對Python來說好像算基本資料結構，起碼是內建資料結構。
**簡單字典教學**
Python的dict(字典)是一種對應(mapping)，將key對應到value，其中key必須是unique，而且是hashable，因為底層是hash table，常用的hashable包含int、tuple、string。value不一定是數值，也可以是任何物件，例如string、list、甚至是另外一個dict。以下用範例介紹簡單的用法，如果要詳細的用法，上網很容易找到教學文件。讀者可以留意到大部分字典的使用方式與list很像，只是list是引用是用[index]，而字典引用是用[key]。
註：Python的dict有個麻煩就是key值不存在時不可取用，否則會引發錯誤，他有一些子類別，例如defaultdict()可以減少這些類麻煩，但這裡我們就不做介紹了。
```python=
d = {1:10, 4:"test"} # initial with 2 items
d = {i:2*i for i in range(10,13)} # initialize
d = {} # initial empty dict
if 3 in d: print(3) # O(1) check existence
if 3 not in d: print("3 not in d")
d[5] = 3 # insert or update
d[2,4] = 100 # tuple as a key
s = d[5] # access, s = 3
d["hello world"] = [1,2,3] # string is hashable
# can map to a list
for v in d: print(d[v], end=',') # dict is iterable
print()
key = list(d.keys()) # all keys
val = list(d.values()) # all values
print(key,val)
p = list(d.items()) # list of tuple (key,value)
print(p)
d.pop(5) # delete key 5
s = d[9] # KeyError, cannot access not existing
```
執行的輸出
```
3 not in d
3,100,[1, 2, 3],
[5, (2, 4), 'hello world'] [3, 100, [1, 2, 3]]
[(5, 3), ((2, 4), 100), ('hello world', [1, 2, 3])]
Traceback (most recent call last):
File "D:\pap325\ch3\dict_demo.py", line 20, in <module>
s = d[9] # KeyError, cannot access not existing
KeyError: 9
```
回到P_3_10這題，以下是使用dict的範例程式，我們不需要做離散化的動作，所以程式比較精簡。但這裡有個小麻煩，前一支程式在做離散化之後就知道總共有多少不同顏色。這裡我們一開始不知道，所以，我們在滑動視窗的過程中，維護好「目前最多顏色的最短視窗」。
most_color是目前最多顏色數量，shortest是目前最多顏色的最短視窗，每一次移動右端調整左端之後，要檢查顏色數是否增加來更新這兩個數值(第20 ~ 24行)。這個部分有個替代手法，就是用len(set(seq))其實就可以求出總共的顏色數量。
在開始滑動視窗前，第9行初始一個字典 d，對每個右端rigth，顏色為color，第11行我們檢查字典中有無color，若有數量加一，否則，將數量d[color]設為1，且他是個新顏色，就順便將n_color加一。接著第17 ~ 19行嘗試縮減左端。
時間複雜度是$O(n)$，這裡的字典動作是高機率$O(1)$，而非絕對worst case的複雜度。
```python=
# P_3_10 shortest all-color range, using dict
n = int(input())
seq = [int(x) for x in input().split()]
most_color = 1; #max num of distinct color
shortest = 1 # shortest range contain most_color
n_color = 0 #num of color in window [left, right]
left = 0
d = {} # dict as a counter, d[color] = num
for right,color in enumerate(seq):
if color in d: # old color
d[color] += 1
else: # new color in window
d[color] = 1
n_color += 1
# shrink left until left color appear only once
while d[seq[left]] > 1: # key always exist
d[seq[left]] -= 1
left += 1
if n_color > most_color: # more color than before
most_color = n_color
shortest = right-left+1
elif n_color == most_color: # check shorter
shortest = min(shortest, right-left+1)
#
print(shortest)
```
上面的寫法，如果不計離散化，時間複雜度都只有$O(n)$，這一題應該已經完美了，但以下還要提出一個比較慢的方法！慢且(台語)！學完快的為什麼還要學慢的呢？解題不是重點，技術才是重點，因為題目千變萬化，只有學到了技術才有用。下面這個方法饒富趣味，而且後面的章節我們也會碰到。
對於一個固定的輸入序列來說，令$f(L)$是長度$L$的連續區段可以擁有的最多顏色數。那麼，P-3-9就是對輸入的$L$計算$f(L)$的值，而P-3-10則是要計算滿足$f(L)=nc$的最小$L$值，其中$nc$是總共的顏色數。函數$f()$明顯有單調性，因為長度更長的情況下，最多擁有的顏色數只會增加或不變，不會變少。因此，如果把P-3-9的程式寫成函數，然後不斷的呼叫$f()$去計算$f(1), f(2),\dots$，直到第一個回傳值不小於nc時，我們就找到了P-3-10的解。
且慢，既然$f()$具單調性，線性搜尋就太遜了，我們當然可以用二分搜。以下是這樣的想法寫出的程式，時間複雜度是多少？如果離散化不計，P-3-9是$O(n)$，長度範圍是$1$ ~ $n$，二分搜會呼叫$O(\log n)$次，所以是$O(n\log n)$。這種策略有時稱為**對答案二分搜**。以下是範例程式。
```python=
# P_3_10 shortest all-color range, repeatedly call P-3-9
# using binary search to find shortest
import bisect
n = int(input())
seq = [int(x) for x in input().split()]
# max num of color of window size w, P-3-9
def w_col(w,seq):
cnt = [0]*len(seq) # number of color i
# initial window
n_color = 0 # number of distinct color
for i,color in enumerate(seq[:w]):
cnt[color] += 1
if cnt[color] == 1: n_color += 1
maxc = 0 # max number of color
# sliding window, [left, right]
# color = seq[i], left = i-l
for left,color in enumerate(seq[w:]):
cnt[color] += 1
if cnt[color] == 1: n_color += 1
lcolor = seq[left]
cnt[lcolor] -= 1
if cnt[lcolor] == 0: n_color -= 1
maxc = max(maxc, n_color)
#
return maxc
#
# coordinate compression
# sort all distinct into dic
v = sorted(seq)
dic = [v[0]]
for p in v[1:]:
if p != dic[-1]: # distinct
dic.append(p)
n_color = len(dic)
# replace color with its rank
seq = [bisect.bisect_left(dic,c) for c in seq]
# end coordinate compression
# using binary search to find the longest invalid length
length = 0
jump = n//2
while jump:
while length+jump<n and w_col(length+jump,seq) < n_color:
length += jump
jump >>= 1
#
print(length+1)
```
接下來兩題與前兩題類似，我們當做習題。
---
##### Q-3-11. 最長的相異色彩帶
有一條細長的彩帶，彩帶區分成$n$格，每一格的長度都是1，每一格都有一個顏色，相鄰可能同色。如果一段彩帶其中的每一格顏色皆相異，則稱為「相異色彩帶」。請計算最長的相異色彩帶的長度。
Time limit: 2秒
輸入格式：第一行為整數$n$，滿足 $n\le 2\times 10^5$；第二行有 $n$ 個以空白間隔的數字，依序代表彩帶從左到右每一格的顏色編號，顏色編號是不超過$n$的非負整數。
輸出：最長的相異色彩帶的長度。
範例輸入：
10
6 4 1 6 0 4 5 0 7 4
範例結果：
5
說明：區間[3, 7]的顏色(1,6,0,4,5)皆不相同。
---
##### Q-3-12. 完美彩帶 (APCS201906)
有一條細長的彩帶，總共有$m$種不同的顏色，彩帶區分成$n$格，每一格的長度都是1，每一格都有一個顏色，相鄰可能同色。長度為m的連續區段且各種顏色都各出現一次，則稱為「完美彩帶」。請找出總共有多少段可能的完美彩帶。請注意，兩段完美彩帶之間可能重疊。
Time limit: 3秒
輸入格式：第一行為整數 $m$ 和 $n$，滿足 $2 \le m \le n \le 2\times 10^5$；第二行有 $n$ 個以空白間隔的數字，依序代表彩帶從左到右每一格的顏色編號，顏色編號是不超過 $10^9$的非負整數，每一筆測試資料的顏色數量必定恰好為 $m$。
輸出：有多少段完美彩帶。
範例輸入：
4 10
1 4 1 7 6 4 4 6 1 7
範例結果：
3
說明：區間[2, 5]是一段完美彩帶，因為顏色4、1、7、6剛好各出現一次，此外，區間[3, 6]與[7, 10]也都是完美彩帶，所以總共有三段可能的完美彩帶。
---
下面的習題與P-3-8類似。
---
##### Q-3-13. X差值範圍內的最大Y差值
輸入平面上$N$個點的座標$(x[i],y[i])$ 以及一個正整數$L$，計算並輸出X差值在$L$內的最大Y差值，亦即 $\max\{|y[i]-y[j]|:\ |x[i]-x[j]|\le L\}$。
Time limit: 3秒
輸入格式：第一行是$N$與$L$，第二行各點的X座標，第三行依序是對應點的Y座標，相鄰數字間以空白隔開。$N\le 2e5$，座標絕對值不超過1e9。
輸出：輸出所求的最大差值。
範例輸入：
10 3
4 1 2 -10 3 5 6 9 7 8
6 1 4 10 3 9 8 1 5 7
範例結果：
7
說明：X距離3以內的最大Y差值是(6,8)與(9,1)，Y值差7。
---
下面這個習題需要一點幾何知識，別擔心，國中就學過了。
---
##### Q-3-14. 線性函數 (@@)
有$N$線性函數$f_i (x)=a_i x+b_i$，$1\le i\le N$。定義$F(x)=\max_i\{ f_i(x)\}$。輸入$c[i]$， $1\le i\le m$，請計算$\sum_{i=1}^{m} F(c[i])$。
Time limit: 2秒
輸入格式：第一行是$N$與$m$。接下來有$N$行，依序每行兩個整數$a_i$與$b_i$，最後一行有$m$個整數$c[1], c[2], …, c[m]$。每一行的相鄰數字間以空白隔開。$N\le 1e5$，$m\le 5e4$，輸入整數絕對值不超過1e8，答案絕對值不超過1e15。
輸出：計算結果。
範例輸入：
4 5
-1 0
1 0
-2 -3
2 -3
4 -5 -1 0 2
範例結果：
15
---
提示：給N個線性函數(一次函數)，另外定義F是這些函數的最大值，現在給$m$個x值，要計算F在這些點的函數值總和，也就是對每一個x值，要計算這些線性函數的最大值。直接的做法全部計算取最大，總共需要$O(mn)$，效率不佳。請看下圖。
藍線是這些線性函數，紅線就是F，他必定會形成一個(向下)凸的形狀，而且是一段一段的，每一段都是原來的某個藍線(函數)，如果我們可以找出這個紅線，計算這些函數值就沒問題了。我們需要一個觀察：若$f$與$g$是兩個線性函數，$f$的斜率小於$g$，那麼，在兩線的交點以前是$f$大，以後是$g$大。我們可以將這些直線根據斜率排序，然後逐一將直線加入F。這一題另外也有分治的演算法可以做，在後續章節中會再出現。
**End of Chapter 3**
Sign in with Wallet
Connect another wallet