如果一个选手比你小还比你强，那你就可以退役了。— 单调队列的原理
注：比你小，就是入队比你晚的，比你强，就是值比你大的，退役，就是你乖乖从队尾出队 （队首是最大值）~
单调队列
单调队列 是一个 双端队列，一般用于维护 连续区间/窗口 内的 最大/小值。
下图给出了 单调队列 维护大小为 的 滑动窗口最大值 示意图：
单调队列工作原理示意图
PS1：目前只知道这个用法，未来随着学习的不断深入，会对本贴进行持续更新 ~
PS2：单调队列 对 多重背包DP 的优化，可将时间复杂度降低至 ，与 0-1 背包 相同，也是 单调队列 的一个经典应用（待补充....，也可能会放到背包问题的学习中 😂） ~
单调队列典型例题/模板
使用 单调队列 维护 滑动窗口最大值，工作原理或代码可参考上图理解~
Python
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
# 单调队列（双端队列）
que = deque()
# 初始化第一个窗口 [0, k - 1]
for i in range(k):
while que and nums[i] >= nums[que[-1]]:
que.pop()
que.append(i)
res = []
res.append(nums[que[0]])
for i in range(k, n):
# 维护窗口 [i - k + 1, i] 内的最大值
# 1. 队尾出队
# 此时新元素比队尾元素大，队尾元素不可能是窗口内的最大值
while que and nums[i] >= nums[que[-1]]:
que.pop()
# 2. 新元素入队
que.append(i)
# 3. 队首出队，
# 维护 que[0] 为窗口内的最大值
while que[0] <= i - k:
que.popleft()
res.append(nums[que[0]])
return res
单调队列优化DP
class Solution:
def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
que = deque()
que.append(0)
for i in range(1, n):
while que and que[0] < i - k:
que.popleft()
# 状态转移
# if dp[que[0]] > 0:
# dp[i] = dp[que[0]] + nums[i]
# else:
# dp[i] = nums[i]
dp[i] = max(dp[que[0]], 0) + nums[i]
while que and dp[que[-1]] <= dp[i]:
que.pop()
que.append(i)
return max(dp)
class Solution:
def maxResult(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
que = deque()
que.append(0)
for i in range(1, n):
while que and que[0] < i - k:
que.popleft()
dp[i] = dp[que[0]] + nums[i]
while que and dp[que[-1]] <= dp[i]:
que.pop()
que.append(i)
return dp[n - 1]
单调队列其它练习
随着 单调队列 练习的增多，而不断增加 ~
Python
# 待补充
Python
# 待补充
Python
# 待补充
评论 (3)
