मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है जिसे अंक और एक पूर्णांक सीमा कहा जाता है, हमें सबसे लंबे गैर-रिक्त उप-सरणी का आकार इस प्रकार खोजना होगा कि इस उप-सरणी के किन्हीं दो मदों के बीच पूर्ण अंतर दी गई सीमा से कम या उसके बराबर हो।
इसलिए, यदि इनपुट संख्या =[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-4| =0 <=4.
-
[4,7] तो |4-7| =3 <=4.
-
[7] तो |7-7| =0 <=4.
अंत में, सबसे लंबे सबअरे का आकार 2 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=0, मैं:=0, जे:=0
-
एक डेक मैक्सडी और दूसरे डेक मिनडी को परिभाषित करें
-
n :=अंकों का आकार
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
जबकि (maxD खाली नहीं है और maxD का अंतिम तत्व
-
maxD से अंतिम तत्व हटाएं
-
-
जबकि (minD खाली नहीं है और minD का अंतिम तत्व> nums[i]), करते हैं -
-
minD से अंतिम तत्व हटाएं
-
-
nums[i] maxD के अंत में डालें
-
minD के अंत में nums[i] डालें
-
जबकि (maxD का पहला तत्व - minD का पहला तत्व)> k, do -
-
अगर nums[j] maxD के पहले तत्व के समान है, तो−
-
मैक्सडी से फ्रंट एलिमेंट हटाएं
-
-
यदि nums[j] minD के पहले तत्व के समान है, तो -
-
minD से फ्रंट एलिमेंट हटाएं
-
-
(जम्मू को 1 से बढ़ाएं)
-
-
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