ধরুন আমাদের একটি অ্যারে আছে। আমাদের A-এর ক্ষুদ্রতম, অ-খালি, সংলগ্ন সাবয়েরের দৈর্ঘ্য খুঁজে বের করতে হবে যার যোগফল কমপক্ষে K। যদি এমন কোনো সাবয়ারে না থাকে, তাহলে -1 ফেরত দিন।
সুতরাং, যদি ইনপুটটি [5,3,-2,2,1] এবং k =6 এর মত হয়, তাহলে আউটপুট হবে 2, আমরা দেখতে পাচ্ছি (5+3)>=6
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=A
এর আকার -
উত্তর :=n + 1, j :=0, যোগফল :=0
-
একটি deque dq
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i
-
যদি i> 0, তাহলে −
-
A[i] :=A[i] + A[i - 1]
-
-
যদি A[i]>=K, তাহলে −
-
উত্তর :=সর্বনিম্ন উত্তর এবং i + 1
-
-
যখন (dq খালি নয় এবং A[i] - প্রথম উপাদান A[dq]>=K), করবেন −
-
উত্তর :=সর্বনিম্ন উত্তর এবং i - dq
এর প্রথম উপাদান -
dq
থেকে সামনের উপাদান মুছুন
-
-
যখন (dq খালি নয় এবং A[i] <=A[dq] এর শেষ উপাদান, do −
-
dq
থেকে শেষ উপাদান মুছুন
-
-
dq
এর শেষে i ঢোকান
-
-
রিটার্ন (যদি উত্তর n + 1 এর মত হয়, তাহলে -1, অন্যথায় ans)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
int j = 0;
int sum = 0;
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;
}
};
main(){
Solution ob;
vector<int> v = {5,3,-2,2,1};
cout << (ob.shortestSubarray(v, 6));
} ইনপুট
{5,3,-2,2,1}, 6 আউটপুট
2
