একটি ইন্টিজার অ্যারে nums এবং লিমিট limit দেওয়া আছে। সবচেয়ে বড় সাবঅ্যারে বের করতে হবে যেন সেটির যেকোনো দুটি এলিমেন্টের মধ্যে অ্যাবসোলিউট ডিফারেন্স limit এর চেয়ে কম বা সমান।
ইনপুট: nums = [8,2,4,7], limit = 4 → আউটপুট: 2 (সাবঅ্যারে [2,4] বা [4,7])
সমাধানের ধাপগুলো (স্লাইডিং উইন্ডো + ডিক):
দুটি ডিক
maxD(নিম্নক্রম) ওminD(বর্ধমান ক্রম) মেইনটেইন করবউইন্ডো প্রসারিত করব
iদিয়েযখন
maxD.front() - minD.front() > limitহয়, উইন্ডো ছোট করবjবাড়িয়েret = max(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 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;
}
};
int main() {
Solution ob;
vector<int> v = {7,8,2,4};
cout << (ob.longestSubarray(v, 4));
}
ইনপুট
{7,8,2,4}, 4
আউটপুট
2
