สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่เรียกว่า nums และขีดจำกัดจำนวนเต็ม เราต้องหาขนาดของอาร์เรย์ย่อยที่ไม่ว่างเปล่าที่ยาวที่สุด เพื่อให้ผลต่างระหว่างสองรายการใดๆ ของอาร์เรย์ย่อยนี้น้อยกว่าหรือเท่ากับขีดจำกัดที่กำหนด
ดังนั้น หากอินพุตมีค่าเท่ากับ 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-4| =0 <=4.
-
[4,7] ดังนั้น |4-7| =3 <=4.
-
[7] ดังนั้น |7-7| =0 <=4.
สุดท้าย ขนาดของ subarray ที่ยาวที่สุดคือ 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0, i :=0, j :=0
-
กำหนดหนึ่ง deque maxD และอีกหนึ่ง deque minD
-
n :=ขนาดของ nums
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ในขณะที่ (ไม่ใช่ maxD ว่างเปล่าและองค์ประกอบสุดท้ายของ maxD
-
ลบองค์ประกอบสุดท้ายออกจาก 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 :=สูงสุดของ 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
