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