[LeetCode] 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/

leetcode - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

문제 유형 : 슬라이딩 윈도우, 투 포인터, 데크(deque)

문제 난이도 : Medium

 

문제

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

정수 배열 nums와 정수 limit이 주어진다. 차가 limit이하인 가장 긴 부분배열의 길이를 구하시오.

 

풀이

투 포인터와 슬라이딩 윈도우로 해결할 수 있다.

최대값들의 인덱스를 저장하는 maxDQ,

최소값들의 인덱스를 저장하는 minDQ를 만든다.

 

right를 순회하면서 maxDQ와 minDQ를 업데이트한다.

maxDQ는 nums[right]보다 maxDQ.back()의 크기가 작거나 같은동안, pop_back()한다. 그뒤 right를 push_back()한다.

minDQ는 nums[right]보다 minDQ.back()의 크기가 크거나 같은동안, pop_back()한다. 그뒤 right를 push_back()한다.

maxDQ의 front에는 항상 부분배열의 최대값의 인덱스가, minDQ의 front에는 항상 부분배열의 최소값의 인덱스가 남아있다.

 

이 두 값의 차가 limit보다 큰동안, left를 오른쪽으로 당겨온다.

maxDQ와 minDQ의 맨 앞이 left보다 작으면 pop_front()한다.

 

ans = max(ans, right - left + 1)로 부분배열의 최대길이를 업데이트한다.

 

코드

C++

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size();
        int ans = 0;
        int left = 0;
        deque<int> maxDQ, minDQ;

        for (int right = 0; right < n; right++) {
            while (!maxDQ.empty() && nums[maxDQ.back()] <= nums[right]) {
                maxDQ.pop_back();
            }
            maxDQ.push_back(right);

            while (!minDQ.empty() && nums[minDQ.back()] >= nums[right]) {
                minDQ.pop_back();
            }
            minDQ.push_back(right);

            while (nums[maxDQ.front()] - nums[minDQ.front()] > limit) {
                left++;
                if (maxDQ.front() < left) {
                    maxDQ.pop_front();
                }
                if (minDQ.front() < left) {
                    minDQ.pop_front();
                }
            }

            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};