मान लीजिए हमारे पास एक सरणी A है। हमें A के सबसे छोटे, गैर-खाली, सन्निहित सबअरे की लंबाई ढूंढनी है जिसका योग कम से कम K है। यदि ऐसा कोई सबअरे नहीं है, तो -1 वापस करें।
उदाहरण के लिए, यदि इनपुट [5,3,-2,2,1] है और k = 6, तो आउटपुट 2 होगा, क्योंकि (5+3) >= 6।
हल करने का दृष्टिकोण
हम मोनोटोनिक डिक (डबल-एंडेड क्यू) का उपयोग करते हैं जिसमें प्रीफिक्स योग होता है:
प्रीफिक्स योग सरणी की गणना करें
बढ़ते प्रीफिक्स योग के सूचकांकों का डिक बनाए रखें
प्रत्येक i के लिए, फ्रंट से जांचें कि क्या A[i] - A[dq.front()] >= K
यदि हां, तो उत्तर अपडेट करें और फ्रंट को पॉप करें
फिर बैक से बड़े प्रीफिक्स योग को पॉप करके मोनोटोनिसिटी बनाए रखें
वर्तमान सूचकांक को डिक में जोड़ें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shortestSubarray(vector<int> &A, int K) {
int n = A.size();
int ans = n + 1;
deque<int> dq;
for (int i = 0; i < n; i++) {
if (i > 0) A[i] += A[i - 1];
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;
}
};
int main(){
Solution ob;
vector<int> v = {5,3,-2,2,1};
cout << (ob.shortestSubarray(v, 6));
return 0;
}
इनपुट
{5,3,-2,2,1}, 6
आउटपुट
2
