前言

本專欄旨在通過(guò)分類學(xué)習(xí)算法，使您能夠牢固掌握不同算法的理論要點(diǎn)。通過(guò)策略性地練習(xí)精選的經(jīng)典題目，幫助您深度理解每種算法，避免出現(xiàn)刷了很多算法題，還是一知半解的狀態(tài)

---

專欄導(dǎo)航

1. 二分查找
2. 回溯（Backtracking）
3. 雙指針
4. 滑動(dòng)窗口
5. 深度優(yōu)先搜索
6. 廣度優(yōu)先搜索
7. 貪心算法
8. 單調(diào)隊(duì)列
9. 堆（Heap）
10. 分治（Divide and Conquer）
11. 動(dòng)態(tài)規(guī)劃

---

算法解析

單調(diào)隊(duì)列是一種特殊的隊(duì)列數(shù)據(jù)結(jié)構(gòu)，其主要特點(diǎn)是保持隊(duì)列元素的單調(diào)性（單調(diào)遞增或單調(diào)遞減）。在單調(diào)隊(duì)列中，新元素的加入可能會(huì)導(dǎo)致隊(duì)列中的一些元素被移除，以維護(hù)隊(duì)列的單調(diào)性。

單調(diào)隊(duì)列通常用于解決滑動(dòng)窗口類問(wèn)題，如尋找窗口內(nèi)的最大值或最小值。使用單調(diào)隊(duì)列能夠在常數(shù)時(shí)間內(nèi)獲取窗口的最大或最小元素，從而有效地優(yōu)化算法的時(shí)間復(fù)雜度。

以下是單調(diào)隊(duì)列的兩種主要操作：

1. 入隊(duì)（Push）：
   當(dāng)新元素加入隊(duì)列時(shí)，從隊(duì)列尾部開(kāi)始，移除所有破壞隊(duì)列單調(diào)性的元素，然后將新元素加入隊(duì)列尾部。對(duì)于單調(diào)遞增隊(duì)列，如果新元素小于隊(duì)尾元素，則隊(duì)尾元素被移除；對(duì)于單調(diào)遞減隊(duì)列，如果新元素大于隊(duì)尾元素，則隊(duì)尾元素被移除。

2. 出隊(duì)（Pop）：
   當(dāng)需要移除隊(duì)列頭部元素時(shí)（例如滑動(dòng)窗口移動(dòng)導(dǎo)致窗口頭部元素不再屬于當(dāng)前窗口），如果隊(duì)頭元素等于需要移除的元素，則將其出隊(duì)。

單調(diào)隊(duì)列可以用雙端隊(duì)列（deque）來(lái)實(shí)現(xiàn)，因?yàn)殡p端隊(duì)列允許從兩端高效地添加和移除元素。

下面是一個(gè)使用 Python 中的 collections.deque 實(shí)現(xiàn)單調(diào)遞減隊(duì)列的示例，該隊(duì)列用于找到滑動(dòng)窗口的最大值：

from collections import dequeclass MonotonicQueue:def __init__(self):self.deque = deque()def push(self, value):# 移除所有小于即將入隊(duì)的值的元素while self.deque and self.deque[-1] < value:self.deque.pop()self.deque.append(value)def max(self):# 隊(duì)列的最大值始終位于隊(duì)頭return self.deque[0]def pop(self, value):# 如果隊(duì)頭元素是即將移除的值，則出隊(duì)if self.deque and self.deque[0] == value:self.deque.popleft()# 示例：滑動(dòng)窗口最大值
def max_sliding_window(nums, k):window = MonotonicQueue()result = []for i, value in enumerate(nums):if i < k - 1:window.push(value)else:# 滑動(dòng)窗口向右移動(dòng)window.push(value)result.append(window.max())  # 記錄當(dāng)前窗口的最大值# 移除窗口最左邊的值window.pop(nums[i - k + 1])return result# 使用示例
nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(max_sliding_window(nums, k))  # 輸出 [3,3,5,5,6,7]

在這個(gè)例子中，我們定義了一個(gè) MonotonicQueue 類來(lái)模擬單調(diào)遞減隊(duì)列，并在滑動(dòng)窗口中使用它來(lái)找到每個(gè)窗口的最大值。當(dāng)新元素加入時(shí)，隊(duì)列中所有小于新元素的值都會(huì)被移除，以保持隊(duì)列的單調(diào)遞減性。當(dāng)窗口滑動(dòng)時(shí)，如果隊(duì)頭的元素是窗口最左邊即將移出窗口的值，則將其從隊(duì)列中移除。

---

實(shí)戰(zhàn)練習(xí)

購(gòu)買水果需要的最少金幣數(shù)

你在一個(gè)水果超市里，貨架上擺滿了玲瑯滿目的奇珍異果。

給你一個(gè)下標(biāo)從 1 開(kāi)始的數(shù)組 prices ，其中 prices[i] 表示你購(gòu)買第 i 個(gè)水果需要花費(fèi)的金幣數(shù)目。

水果超市有如下促銷活動(dòng)：

如果你花費(fèi) price[i] 購(gòu)買了水果 i ，那么接下來(lái)的 i 個(gè)水果你都可以免費(fèi)獲得。
注意 ，即使你 可以 免費(fèi)獲得水果 j ，你仍然可以花費(fèi) prices[j] 個(gè)金幣去購(gòu)買它以便能免費(fèi)獲得接下來(lái)的 j 個(gè)水果。

請(qǐng)你返回獲得所有水果所需要的 最少 金幣數(shù)。

示例 1：
輸入：prices = [3,1,2]
輸出：4

解釋：你可以按如下方法獲得所有水果：

• 花 3 個(gè)金幣購(gòu)買水果 1 ，然后免費(fèi)獲得水果 2 。
• 花 1 個(gè)金幣購(gòu)買水果 2 ，然后免費(fèi)獲得水果 3 。
• 免費(fèi)獲得水果 3 。
  注意，雖然你可以免費(fèi)獲得水果 2 ，但你還是花 1 個(gè)金幣去購(gòu)買它，因?yàn)檫@樣的總花費(fèi)最少。
  購(gòu)買所有水果需要最少花費(fèi) 4 個(gè)金幣。

示例 2：
輸入：prices = [1,10,1,1]
輸出：2

解釋：你可以按如下方法獲得所有水果：

• 花 1 個(gè)金幣購(gòu)買水果 1 ，然后免費(fèi)獲得水果 2 。
• 免費(fèi)獲得水果 2 。
• 花 1 個(gè)金幣購(gòu)買水果 3 ，然后免費(fèi)獲得水果 4 。
• 免費(fèi)獲得水果 4 。
  購(gòu)買所有水果需要最少花費(fèi) 2 個(gè)金幣。

提示：
1 <= prices.length <= 1000
1 <= prices[i] <= 105

官方題解

---

環(huán)形子數(shù)組的最大和

給定一個(gè)長(zhǎng)度為 n 的環(huán)形整數(shù)數(shù)組 nums ，返回 nums 的非空 子數(shù)組 的最大可能和 。

環(huán)形數(shù)組 意味著數(shù)組的末端將會(huì)與開(kāi)頭相連呈環(huán)狀。形式上， nums[i] 的下一個(gè)元素是 nums[(i + 1) % n] ， nums[i] 的前一個(gè)元素是 nums[(i - 1 + n) % n] 。

子數(shù)組 最多只能包含固定緩沖區(qū) nums 中的每個(gè)元素一次。形式上，對(duì)于子數(shù)組 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：
輸入：nums = [1,-2,3,-2]
輸出：3
解釋：從子數(shù)組 [3] 得到最大和 3

示例 2：
輸入：nums = [5,-3,5]
輸出：10
解釋：從子數(shù)組 [5,5] 得到最大和 5 + 5 = 10

示例 3：
輸入：nums = [3,-2,2,-3]
輸出：3
解釋：從子數(shù)組 [3] 和 [3,-2,2] 都可以得到最大和 3

提示：
n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104???????

官方題解