好文集ChatGPT Plus¥119

一个单调队列模版，刷掉 5 道 LeetCode 硬题

山景城小路·约 3 分钟阅读
文章目录

核心思想一句话：候选人排队，弱的直接出局。

队列里存下标、永远保持单调：新人来了，把队尾不如他的全踢掉；下标过期了，从队首踢掉。队首永远是当前窗口的最优解。

通用模版（递减队列，求窗口最大）

from collections import deque

dq = deque()  # 存下标，队列单调
for i, x in enumerate(nums):
    while dq and dq[0] < i - k + 1:  # 1. 过期：踢队首
        dq.popleft()
    while dq and nums[dq[-1]] <= x:  # 2. 单调：踢队尾
        dq.pop()
    dq.append(i)
    best = nums[dq[0]]  # 3. 队首即答案

三步走：过期踢队首，单调踢队尾，队首即答案。

下面五道题全是这个模版的换皮 👇

1️⃣ LC 239 滑动窗口最大值（Hard）：模版本体

窗口大小 k，每走一步输出窗口最大值。把模版里的 best 收集起来就是答案。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()
        res = []
        for i, x in enumerate(nums):
            while dq and dq[0] <= i - k:
                dq.popleft()
            while dq and nums[dq[-1]] <= x:
                dq.pop()
            dq.append(i)
            if i >= k - 1:
                res.append(nums[dq[0]])
        return res

2️⃣ LC 1696 跳跃游戏 VI（Medium）：dp 套模版

dp[i] = nums[i] + 窗口 [i-k, i-1] 内最大的 dp

"窗口最大值"四个字一出现，模版直接套。

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        dq = deque([0])
        for i in range(1, n):
            while dq and dq[0] < i - k:
                dq.popleft()
            dp[i] = nums[i] + dp[dq[0]]
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)
        return dp[-1]

3️⃣ LC 1425 带限制的子序列和（Hard）：1696 的双胞胎

和 1696 同构，区别只有一处：子序列可以从任意位置重新开始，所以前面是负的就不要：

dp[i] = nums[i] + max(0, 队首 dp)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dq = deque()
        ans = float('-inf')
        for i, x in enumerate(nums):
            while dq and dq[0] < i - k:
                dq.popleft()
            dp[i] = x + max(0, dp[dq[0]] if dq else 0)
            ans = max(ans, dp[i])
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)
        return ans

4️⃣ LC 862 和至少为 K 的最短子数组（Hard）：前缀和 + 递增队列

nums 有负数，滑窗双指针失效。

转成前缀和：找 j < i 使 pref[i] - pref[j] >= k 且 i - j 最短。

维护 pref 递增的队列：队首一旦满足条件就出队结算。这个 j 在当前 i 已经拿到它能贡献的最短长度，以后只会更长，直接扔掉。

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pref = [0] * (n + 1)
        for i, x in enumerate(nums):
            pref[i + 1] = pref[i] + x
        dq = deque()  # pref 递增
        ans = float('inf')
        for i, p in enumerate(pref):
            while dq and p - pref[dq[0]] >= k:
                ans = min(ans, i - dq.popleft())
            while dq and pref[dq[-1]] >= p:
                dq.pop()
            dq.append(i)
        return ans if ans != float('inf') else -1

5️⃣ LC 1438 绝对差不超过限制的最长连续子数组（Medium）：双队列，这就是那 0.5 道

窗口内 max - min <= limit。

两个队列同时维护：一个递减管最大值，一个递增管最小值。超限就缩左边界，直到合法为止。

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        maxdq = deque()  # 递减，队首最大
        mindq = deque()  # 递增，队首最小
        left = 0
        ans = 0
        for right, x in enumerate(nums):
            while maxdq and nums[maxdq[-1]] <= x:
                maxdq.pop()
            maxdq.append(right)
            while mindq and nums[mindq[-1]] >= x:
                mindq.pop()
            mindq.append(right)
            while nums[maxdq[0]] - nums[mindq[0]] > limit:
                left += 1
                if maxdq[0] < left:
                    maxdq.popleft()
                if mindq[0] < left:
                    mindq.popleft()
            ans = max(ans, right - left + 1)
        return ans

一句话记住

过期踢队首，单调踢队尾，队首即答案。

认出"窗口最值"四个字，模版直接套，O(n) 收工。

题目链接

全文完
查看原文
发现更多