862. 和至少为 K 的最短子数组

Difficulty

Hard

法 1单调队列

思路

[python3] O(n) 前缀和图解 - 和至少为 K 的最短子数组 - 力扣（LeetCode）

我们定义前缀和数组为P，那么我们现在的目标就是找出差值大于等于k，且离得最近的两个值。

————看出来了吧，这是什么？这是前缀和微分呀。

事实上，前缀和的构建过程就是积分，积分的离散的微分（原数组）的局部和，那不就是积分的局部导数。

我们用图片来直观地解释：柱状图表示原数组，折线图表示前缀和数组。（下标不知道怎么改，反正是求差，不影响理解）

我们可以将两个条件转换：

原数组 i-j 之间的和至少为K -> 前缀和数组 sum_j - sum_i 的差至少为K。

满足1的条件下，原数组i与j尽可能近 -> 前缀和数组i与j尽可能近。（注意！我虽然用微分来形象化地表述这个条件，但这道题不能变为“找到最大的微分位置”！因为我们的差值只需要满足大于K，而不是差值尽量大）

假设我们将K设置为2，来模拟一下过程：

当j为3时，前缀和数组终于能找到满足差值大于2的i了。因此，此时找到一组答案。此时这个微分我们写为

下面，我们往右遍历j，当j为4时，我们确定微分的右边的点向右走了一步。我们已经记录过了，我们思考一下，当是一种答案的前提下，如果我们的目标是找到更大的微分，那么我们肯定不再需要把i的位置向左看了。因此，当j向右移动后，我们不再需要考虑之前i左边的任何信息。因为就算i左边的某个点能满足第一个条件，其连成的斜率也一定比小。这时我们能找到最大的微分

类似这种思路，我们一直找，再也没有发现一个能大于的微分值。突然，前缀和数组竟然不是递增了。我们来到了一个比前一个还小的j。我们可以直观地看到，如果前面前缀和比这个值大，那无论如何不可能找到一个正的，更别提大于K了，因此，我们不用考虑小于sum_j的任何i。这就是维持一个单调队列的意义。

最后，以此类推，当j=7时，我们与i_1找到，实际上与\nabla_2相同，不更新答案。j=8时，i_2与j连成，是见过最大的。

注意！！最大不一定在本题中最优！本题限定了K=2

题解


class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        res = float('inf')
        # 先计算前缀和
        prefix = [0] * (len(nums) + 1)
        for i in range(0, len(nums)):
            prefix[i+1] = prefix[i] + nums[i]

        q = deque()

        for i in range(len(nums)+1):
            while q and prefix[i] - prefix[q[0]] >= k:
                res = min(res, i-q.popleft())
            # 如果 
            while q and prefix[q[-1]] > prefix[i]:
                q.pop()
            q.append(i)

        return res if res != float('inf') else -1


class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        prefix = [0 for _ in range(0, len(nums)+1)]
        for i in range(1, len(prefix)):
            prefix[i] = prefix[i-1] + nums[i-1]

        queue = deque()
        res = len(nums)+1
        for i in range(0, len(prefix)):
            # 如果 prefix[i] < prefix[queue[-1]], 那么 prefix[i]比另一个更可能是起点
            while queue and prefix[i] < prefix[queue[-1]]:
                queue.pop()

            # 满足条件了，不断的缩减
            while queue and prefix[i] - prefix[queue[0]] >= k:
                res = min(res, i-queue.popleft())

            queue.append(i)

        return res if res != len(nums)+1 else -1