862. 和至少為 K 的最短子數組

思路

給定一個陣列，找出和 $\geq{k}$ 的最短非空子陣列，不存在返回-1。
陣列當中的數字有正有負，當陣列變得更長時，和並不會因此遞增，不能單純用滑動窗口解。

為了加速計算，首先用前綴和來快速求一個子陣列的總和。
假設現在陣列為 $[1,1,1,6,8,2,9],k=10$ ，前綴和陣列 $[0,1,2,3,9,17,\dots]$ 。

• 在前綴和數組中，數字 17 要找的目標是 $17-10=7$ ，好找到固定右端點時最佳的解答。（找的目標 $\leq7$ ）。
  • 找到前綴和中的 3，對應到原先陣列是 $[6,8]$ （左開右閉）

從 $0\sim{i}$ ，總和為 $x$ ，從 $i$ 往左延展，要盡量短，並且 $\geq{k}$ 。
相當於要知道一個前綴和 $\leq{x-k}$ ，且盡量靠右。
$[1,1,1,6,8,2,9,1,5,4,1],k=10$
準備一個雙端隊列，要求左到右從小到大，放入前綴和的數字。
如果隊列的尾端減去頭 $\geq{10}$ ，嘗試縮減，並列入參考答案。

有負數的情況： $[6,5,3,-8,9,2]$ ， $k=100$
連續加入幾個數字： $[0,6,11,14]$ ，然後要加入一個 $6$ ，此時的數字相比尾端數字，是比較小的。此時要連續淘汰三個數字，再將 6 加進來。
這樣做的原因是：

1. 假如後面有個前綴和 $x$ ：減去 6 不達標，那麼減去 11, 14 肯定也不達標。
2. 假如後面有個前綴合 $x$ ：減去 6 達標，也不需要考慮 11, 14。
   因為後面還有個 6，位置靠後，對應到更短的長度，只需保留後面的 6 即可。

舉例

$[5,4,3,-4,6,3,7],k=10$ 。

• deque = [0,5,9]，加入前綴和時，減去頭部都不滿足條件。
• deque = [0,5,9,12] $\to$ [5,9,12]
  • 12 - 0 達標，丟掉 $0$ ，列入參考答案，res = 3。
  • 12 - 5 不達標，停止。
• deque = [5,9,12,8] $\to$ [5,8]
  • 將比自己小的數字清除，最後將自己加入隊列。
  • 8 - 5 不達標，停止。
• deque = [5,8,14]
  • 14 - 5 不達標，停止。
• deque = [5,8,14,17] $\to$ [8,14,17]
  • 17 - 5 達標，丟掉 $5$ ，列入參考答案，res = min(3,5)。
  • 17 - 8 不達標，停止。
• deque = [8,14,17,24] $\to$ [17,24]
  • 24 - 8 達標，丟掉 $8$ ，列入參考答案，res = min(3,3)。
  • 24 - 14 達標，丟掉 $14$ ，列入參考答案，res = min(3,2)。

程式碼

1. 前綴和 + 單調隊列

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        int res = INT_MAX;
        deque<int> dq;
        
        // 前綴和
        vector<long long> preSum(n + 1);
        for(int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        for(int i = 0; i <= n; i++) {
            // 尾端可能為空 (比如第一個數字進入時) 
            while(!dq.empty() && preSum[dq.back()] >= preSum[i]) { 
                // 如果尾端的前綴合比較大，就更沒機會 >= k
                // 位置靠後，數值又小，preSum[i] 全方位比尾端好
                dq.pop_back();
            }
            while(!dq.empty() && preSum[i] - preSum[dq.front()] >= k) {
                // 當前位置減去最小值, 如果 >= k, 列入參考
                res = min(res, i - dq.front());
                dq.pop_front();
            }
            dq.push_back(i);
        }
        return res == INT_MAX ? -1 : res;
    }
};

2. 前綴和 + 單調隊列 數組實現

class Solution {
private:
    static const int MX = 1e5 + 2; // 前綴合數組一共有 n + 1 個數字
    int dq[MX];
    long long preSum[MX];
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        int res = INT_MAX;
        
        // 前綴和
        for(int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int left = 0, right = 0;        
        for(int i = 0; i <= n; i++) {
            // 尾端可能為空 (比如第一個數字進入時) 
            while(left != right && preSum[dq[right - 1]] >= preSum[i]) { 
                // 如果尾端的前綴合比較大，就更沒機會 >= k
                // 位置靠後，數值又小，preSum[i] 全方位比尾端好
                right--;
            }
            while(left != right && preSum[i] - preSum[dq[left]] >= k) {
                // 當前位置減去最小值, 如果 >= k, 列入參考
                res = min(res, i - dq[left]); // 左開右閉
                left++;
            }
            dq[right++] = i;
        }
        return res == INT_MAX ? -1 : res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$