ซับอาร์เรย์สั้นที่สุดที่ผลรวมมากกว่าหรือเท่ากับ K ใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A หาความยาวซับอาร์เรย์ติดต่อกันสั้นที่สุดที่ผลรวม ≥ K หากไม่มีคืน -1

ตัวอย่าง

A = [5,3,-2,2,1], K = 6 → Output: 2 (ซับอาร์เรย์ [5,3])

แนวทางแก้ปัญหา: Monotonic Deque + Prefix Sum

คำนวณ prefix sum: P[i] = A[0]+...+A[i]
ต้องการหา i

รักษา deque ของ index ที่ P[index] เพิ่มขึ้น (monotonic increasing):

• ขยายขวา: เพิ่ม i ลบ index ท้ายที่ P[i] ≤ P[ท้าย] (เพราะ P[i] ดีกว่า)
• หดซ้าย: ถ้า P[i] - P[หน้า] ≥ K → อัปเดตคำตอบ, pop front

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int n = A.size(), ans = n+1;
        deque<int> dq;
        
        for(int i=0; i 0) A[i] += A[i-1]; // prefix sum in-place
            if(A[i] >= K) ans = min(ans, i+1);
            
            while(!dq.empty() && A[i] - A[dq.front()] >= K) {
                ans = min(ans, i - dq.front());
                dq.pop_front();
            }
            while(!dq.empty() && A[i] <= A[dq.back()]) dq.pop_back();
            dq.push_back(i);
        }
        return ans == n+1 ? -1 : ans;
    }
};

ความซับซ้อน

• เวลา: O(n) (แต่ละ index เข้า/ออก deque สูงสุด 1 ครั้ง)
• พื้นที่: O(n)