🔗 🔴 862. Shortest Subarray with Sum at Least K

Problem Statement

題目簡述

給定一個整數陣列 numsnums 和一個整數 kk，請找出 numsnums 中和至少為 kk 的最短非空子陣列的長度。
若不存在此類子陣列，則返回 −1-1。

Constraints

約束條件

  • 1≤nums.length≤1051 \le \text{nums.length} \le 10^5
  • −105≤nums[i]≤105-10^5 \le \text{nums}[i] \le 10^5
  • 1≤k≤1091 \le k \le 10^9

思路：單調佇列與前綴和

轉換問題：前綴和

為了方便處理區間和，我們引入前綴和。
定義前綴和陣列 ss，其中 s[0]=0s[0] = 0，且對於 1≤i≤n1 \le i \le n：

s[i]=∑x=0i−1nums[x]s[i] = \sum_{x=0}^{i-1} \text{nums}[x]

這樣一來，任何一個子陣列 nums[l…r]\text{nums}[l \dots r]（其中 0≤l≤r<n0 \le l \le r < n）的元素和，都可以表示為兩個前綴和之差：

∑x=lrnums[x]=s[r+1]−s[l]\sum_{x=l}^{r} \text{nums}[x] = s[r+1] - s[l]

則區間 [l,r][l, r] 的元素和至少為 kk 的條件等價於：

s[r+1]−s[l]≥k(0≤l≤r<n)s[r+1] - s[l] \ge k \quad (0 \le l \le r < n)

問題等價於：尋找一對前綴和下標 (i,j)(i, j)，滿足 i<ji < j，使得 s[j]−s[i]≥ks[j] - s[i] \ge k，且 j−ij - i 最小。

固定右端點 jj，問題變成：在 jj 的左側，尋找一個滿足 s[i]≤s[j]−ks[i] \le s[j] - k 的最大下標 ii。

為什麼普通的滑動視窗（雙指標）會失效？

在 209. Minimum Size Subarray Sum 中，由於陣列中的元素均為正數，前綴和具有單調遞增的性質。這使我們可以用雙指標（滑動視窗）維護：當視窗內元素和至少為 kk 時，我們可以直接收縮左邊界，因為更右邊的右邊界只會讓區間和更大，不用擔心漏掉答案。

然而，本題的元素可以為負數。這意味著前綴和不再具有單調性。即使我們增加左邊界，子陣列的和也可能因為移除了負數而變得更大；或者增加右邊界時，和反而因為加入了負數而變小。這使得滑動視窗的單調收縮邏輯徹底失效。

尋找優化：單調佇列的雙重篩選

既然 O(n2)\mathcal{O}(n^2) 的暴力枚舉瓶頸在於保留了太多「無用」的左端點，我們如何一邊遍歷右端點 jj，一邊高效篩選左端點 ii？

我們可以用一個雙端佇列（Deque） 來維護候選的左端點下標。為了實現 O(n)\mathcal{O}(n) 的均攤複雜度，佇列需要進行雙向彈出優化：

關鍵觀察：左端點的雙重篩選機制

1. 隊尾彈出：剔除被支配的劣勢解（維護單調性）

假設佇列中已有兩個候選左端點 xx 和 yy，滿足 x<yx < y。
如果此時發現 s[x]≥s[y]s[x] \ge s[y]，那麼 xx 將永遠不可能成為最優的左端點。

證明：為什麼 xx 被 yy 支配？

  • 對於任何未來的右端點 j′>yj' > y，如果 xx 能與 j′j' 配對（即 s[j′]−s[x]≥ks[j'] - s[x] \ge k），由於 s[x]≥s[y]s[x] \ge s[y]，我們必定也有 s[j′]−s[y]≥s[j′]−s[x]≥ks[j'] - s[y] \ge s[j'] - s[x] \ge k，說明 yy 也能與 j′j' 配對。
  • 由於 x<yx < y，子陣列 [y,j′−1][y, j'-1] 的長度 j′−yj' - y 必定比 [x,j′−1][x, j'-1] 的長度 j′−xj' - x 更短。
  • 因此，只要有 yy 存在，在它左邊且前綴和更大的 xx 就失去了存在的價值。我們可以直接將 xx 從佇列尾部彈出。
  • 操作：每次將當前前綴和 sjs_j 加入佇列前，從隊尾開始比較，將所有前綴和大於等於 sjs_j 的下標彈出。這保證了佇列中的前綴和是嚴格單調遞增的。

2. 隊首彈出：完成歷史使命的及時撤退（更新答案）

由於佇列內的前綴和是單調遞增的，隊首 q0q_0 是前綴和最小、最容易滿足配對條件的候選。

  • 如果當前的右端點前綴和 sjs_j 滿足 sj−s[q0]≥ks_j - s[q_0] \ge k，那麼 j−q0j - q_0 就是一個候選的最短長度，我們更新全域最值。
證明：為什麼 q0q_0 可以永久彈出？

  • 因為對於未來的任何右端點 j′>jj' > j，即使 j′j' 也能與 q0q_0 配對，其形成的子陣列長度 j′−q0j' - q_0 也必定大於 j−q0j - q_0。
  • 由於我們要求的是最短子陣列，未來的配對絕不可能刷新最短長度的紀錄。
  • 操作：從隊首開始，只要滿足 sj−s[q0]≥ks_j - s[q_0] \ge k，就更新答案並將隊首彈出，直到不滿足條件為止。
核心套路：枚舉右，維護左

本題是「枚舉右端點，用單調佇列維護左端點」的經典模型。兩個方向的彈出各司其職：

  • 隊尾彈出：剔除被支配的劣勢左端點，保證佇列單調遞增；
  • 隊首彈出：完成配對即永久移除，避免重複計算。

每個下標至多入隊出隊一次，總時間複雜度優化至 O(n)\mathcal{O}(n)。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)。前綴和計算 O(n)\mathcal{O}(n)；遍歷過程每個下標至多入隊出隊各一次，均攤 O(1)\mathcal{O}(1)。
  • 空間複雜度：O(n)\mathcal{O}(n)。

類題：

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # s[j] 表示 nums 的前 j 個元素之和，s[0] = 0
        s = list(accumulate(nums, initial=0))

        ans = n + 1
        q = deque()  # 雙端佇列，儲存前綴和的下標
        for j, sj in enumerate(s):
            # 1. 隊首彈出：若當前區間和 s[j] - s[q[0]] >= k，則找到一個可行解
            # 由於我們求的是「最短」子陣列，q[0] 之後再與更右邊的右端點配對，長度只會更長
            # 因此 q[0] 已完成其歷史使命，可永久彈出並更新答案
            while q and sj - s[q[0]] >= k:
                ans = min(ans, j - q[0])
                q.popleft()
            
            # 2. 隊尾彈出：若當前前綴和 s[j] <= s[q[-1]]
            # 由於當前下標 j 既靠右，前綴和又更小，隊尾元素已被當前元素支配（不可能再作為最優左端點）
            # 我們將隊尾彈出，以維護佇列中前綴和的嚴格單調遞增性質
            while q and sj <= s[q[-1]]:
                q.pop()

            q.append(j)

        return ans if ans <= n else -1