ধরুন আমাদের কাছে একটি পূর্ণসংখ্যার অ্যারে আছে যাকে nums বলা হয় এবং একটি পূর্ণসংখ্যা সীমা, আমাদেরকে দীর্ঘতম অ-খালি সাবয়ারের আকার খুঁজে বের করতে হবে যেমন এই সাবয়ারের যেকোনো দুটি আইটেমের মধ্যে পরম পার্থক্য প্রদত্ত সীমার কম বা সমান।
সুতরাং, যদি ইনপুট হয় সংখ্যা =[8,2,4,7], সীমা =4, তাহলে আউটপুট হবে 2, এর কারণ −
-
[8] তাই |8-8| =0 <=4।
-
[8,2] তাই |8-2| =6> 4।
-
[8,2,4] তাই |8-2| =6> 4।
-
[8,2,4,7] তাই |8-2| =6> 4।
-
[2] তাই |2-2| =0 <=4।
-
[2,4] তাই |2-4| =2 <=4.
-
[2,4,7] তাই |2-7| =5> 4।
-
[৪] তাই |4-4| =0 <=4।
-
[4,7] তাই |4-7| =3 <=4।
-
[7] তাই |7-7| =0 <=4।
অবশেষে, দীর্ঘতম সাবয়ারের আকার হল 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=0, i :=0, j :=0
-
একটি deque maxD এবং আরেকটি deque minD
সংজ্ঞায়িত করুন -
n :=সংখ্যার আকার
-
আরম্ভ করার জন্য i :=0, যখন i
-
যখন (maxD খালি নয় এবং maxD
-
maxD
থেকে শেষ উপাদান মুছুন
-
-
যখন (minD খালি নয় এবং minD> nums[i] এর শেষ উপাদান), −
-
MinD
থেকে শেষ উপাদান মুছুন
-
-
maxD
এর শেষে nums[i] সন্নিবেশ করান -
minD
এর শেষে nums[i] সন্নিবেশ করান -
যখন (maxD-এর প্রথম উপাদান - minD-এর প্রথম উপাদান)> k, do −
-
যদি nums[j] maxD-এর প্রথম উপাদানের মতো হয়, তাহলে−
-
maxD
থেকে সামনের উপাদান মুছুন
-
-
যদি nums[j] minD এর প্রথম উপাদানের মত হয়, তাহলে −
-
minD
থেকে সামনের উপাদান মুছুন
-
-
(j 1 দ্বারা বাড়ান)
-
-
ret :=ret এর সর্বোচ্চ এবং (i - j + 1)
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestSubarray(vector<int>& nums, int k) {
int ret = 0;
int i = 0;
int j = 0;
deque<int> maxD;
deque<int> minD;
int n = nums.size();
for (int i = 0; i < n; i++) {
while (!maxD.empty() && maxD.back() < nums[i])
maxD.pop_back();
while (!minD.empty() && minD.back() > nums[i])
minD.pop_back();
maxD.push_back(nums[i]);
minD.push_back(nums[i]);
while (maxD.front() - minD.front() > k) {
if (nums[j] == maxD.front())
maxD.pop_front();
if (nums[j] == minD.front())
minD.pop_front();
j++;
}
ret = max(ret, i - j + 1);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {7,8,2,4};
cout << (ob.longestSubarray(v, 4));
} ইনপুট
{7,8,2,4}, 4 আউটপুট
2
