nums라고 하는 정수 배열과 정수 제한이 있다고 가정하고 비어 있지 않은 가장 긴 하위 배열의 크기를 찾아 이 하위 배열의 두 항목 간의 절대 차이가 주어진 제한보다 작거나 같도록 해야 합니다.
따라서 입력이 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 :=숫자 크기
-
initialize i :=0의 경우, i
-
동안 (maxD가 비어 있지 않고 maxD
-
maxD에서 마지막 요소 삭제
-
-
(minD가 비어 있지 않고 minD> nums[i]의 마지막 요소가 아님), 다음을 수행합니다. -
-
minD에서 마지막 요소 삭제
-
-
maxD
끝에 nums[i] 삽입 -
minD
끝에 nums[i] 삽입 -
동안 (maxD의 첫 번째 요소 - minD의 첫 번째 요소)> k, do −
-
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