資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中長度最長的連續子陣列，其絕對差小於或等於限制
假設我們有一個名為 nums 的整數陣列和一個整數 limit，我們需要找到最長非空子陣列的大小，使得該子陣列中任意兩個元素的絕對差小於或等於給定的 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 加 1），執行：
當 (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 := 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
447 次瀏覽
