1.題目
給你一個整數陣列 nums ，和一個表示限制的整數 limit，請你回傳最長連續子陣列的長度，該子陣列中的任意兩個元素之間的絕對差必須小于或者等于 limit ，
如果不存在滿足條件的子陣列，則回傳 0 ，
示例 1：
輸入：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 ，
示例 2：
輸入：nums = [10,1,2,4,7,2], limit = 5
輸出：4
解釋：滿足題意的最長子陣列是 [2,4,7,2]，其最大絕對差 |2-7| = 5 <= 5 ，
示例 3：
輸入：nums = [4,2,2,2,4,4,2,2], limit = 0
輸出：3
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
2.暴力破解的優化方法（雙指標）
2.1原理
先來說一下暴力破解，暴力破解就是逐個去比較，一旦出現不符合的時候，我們便向前挪動，找出最長的子陣列，
其實我們沒必要依次去比較，我們只要保證這個子陣列中最大的值減去最小的值不大于limit，這樣就可以保證子陣列中所有的數都符合要求，
所以我們一開始就記錄最大值和最小值的數值和位置，左指標保持不動，讓右指標先移動，只要右指標的值在最小值和最大值的中間，那么肯定是符合的題意的，只有右指標指向的元素大于最大值或者小于最小值時，才可能會出現不符合題意的現象，一旦出現不符合題意的現象，就意味著最大值和最小值不符合，那么我們判斷是哪個值靠前，我們就讓左指標移動過來，然后重新給最小值或者最大值賦值，接下來讓右指標繼續移動，如果仍不符合，左指標會繼續移動，長度肯定會小于我們之前得出的最長的子陣列，所以我們一旦遇到不符合的情況，只要讓左指標移動一次就好，如果遇到右指標等于最大值或最小值時，我們也要重新給最大值或最小值賦值，這樣就可以省下再尋找這個元素的時間，
2.2代碼
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int left = 0, right = 0;
int max = nums[0], min = nums[0];
int maxp = 0, minp = 0;
int len = 0;
while(right < nums.size()) {
if(nums[right] >= max) {
max = nums[right];
maxp = right;
}
else if(nums[right] <= min) {
min = nums[right];
minp = right;
}
if(max - min <= limit) {
if(right - left + 1 > len)
len = right - left + 1;
}
else {
if(maxp > minp) {
left = minp + 1;
min = nums[left];
minp = left;
for(int i = left + 1; i <= right; i++) {
if(nums[i] <= min) {
min = nums[i];
minp = i;
}
}
}
else {
left = maxp + 1;
max = nums[left];
maxp = left;
for(int i = left + 1; i <= right; i++) {
if(nums[i] >= max) {
max = nums[i];
maxp = i;
}
}
}
}
right++;
}
return len;
}
};
3.滑動視窗+有序集合
3.1前置知識
平衡樹：平衡樹(Balance Tree，BT) 指的是，任意節點的子樹的高度差都小于等于1，常見的符合平衡樹的有，B樹（多路平衡搜索樹）、AVL樹（二叉平衡搜索樹）等，平衡樹可以完成集合的一系列操作, 時間復雜度和空間復雜度相對于“2-3樹”要低，在完成集合的一系列操作中始終保持平衡，為大型資料庫的組織、索引提供了一條新的途徑，
3.2原理
和我個人的暴力破解優化是相同的做法，保證最大值減去最小值不大于limit，在判斷最大值和最小值的時候利用了平衡樹的原理，在重新設定最大值和最小值的程序中省去了時間，原來是n，利用平衡樹是logn的時間復雜度，總時間復雜度是nlogn
3.3代碼
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
multiset<int> s;
int n = nums.size();
int left = 0, right = 0;
int ret = 0;
while (right < n) {
s.insert(nums[right]);
while (*s.rbegin() - *s.begin() > limit) {
s.erase(s.find(nums[left++]));
}
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/jue-dui-chai-bu-chao-guo-xian-zhi-de-zui-5bki/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
4.滑動視窗+單調佇列
4.1前置知識
單調佇列：單調佇列，即單調遞級訓單調遞增的佇列，使用頻率不高，但在有些程式中會有非同尋常的作用，
4.2原理
道理還是一樣，依然是找最大值和最小值，在這里用了兩個單調佇列，來存盤最大值和最小值，保證兩個佇列的第一個元素符合要求即可，不符合，開始讓元素退出佇列，直到符合條件為止，
4.3代碼
class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
deque<int> queMax, queMin;
int n = nums.size();
int left = 0, right = 0;
int ret = 0;
while (right < n) {
while (!queMax.empty() && queMax.back() < nums[right]) {
queMax.pop_back();
}
while (!queMin.empty() && queMin.back() > nums[right]) {
queMin.pop_back();
}
queMax.push_back(nums[right]);
queMin.push_back(nums[right]);
while (!queMax.empty() && !queMin.empty() && queMax.front() - queMin.front() > limit) {
if (nums[left] == queMin.front()) {
queMin.pop_front();
}
if (nums[left] == queMax.front()) {
queMax.pop_front();
}
left++;
}
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};
作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/jue-dui-chai-bu-chao-guo-xian-zhi-de-zui-5bki/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262001.html
標籤：其他
下一篇：淺談深度學習的落地問題