題目描述: 給定一個整數陣列 nums 和一個正整數 k,找出最短的非空子陣列,使其元素之和至少為 k。如果不存在這樣的子陣列,返回 -1。注意陣列中可能有負數。
解題思路:
時間複雜度:O(n) — 每個索引最多入隊和出隊各一次
空間複雜度:O(n) — 前綴和陣列和雙端佇列
1. Compute prefix sum array: prefix[0] = 0, prefix[i+1] = prefix[i] + nums[i]
2. Initialize monotonic deque (stores indices) and ans = infinity
3. For j from 0 to n:
a. While deque not empty AND prefix[j] - prefix[front] >= k:
- Update ans = min(ans, j - front)
- Pop front (this start index is consumed)
b. While deque not empty AND prefix[j] <= prefix[back]:
- Pop back (current j dominates as a start point)
c. Push j to back of deque
4. Return ans if <= n, else -1二分搜尋 + 前綴和排序:對於每個 j,二分搜尋最大的 i 使得 prefix[j] - prefix[i] >= k。但需要維護前綴和的有序結構(如 BIT 或平衡 BST),時間複雜度 O(n log n)。
堆(Priority Queue):將 (prefix[i], i) 放入最小堆。對每個 j,從堆頂取出最小前綴和嘗試配對。時間複雜度 O(n log n),但實作較直覺。