[LeetCode] 2762. Continuous Subarrays

https://leetcode.com/problems/continuous-subarrays/description/

leetcode - Continuous Subarrays

문제 유형: 슬라이딩 윈도우, 모노토닉 스택, 모노토닉 큐, 모노토닉 데크

문제 난이도: Medium

 

문제

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

• Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number of continuous subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

 

정수 배열 nums가 주어진다.

nums의 부분배열의 모든 요소 쌍의 차가 2 이하이면, continuous하다고 한다.

continuous한 부분배열의 개수를 구하시오.

 

풀이

 

두 개의 deque를 만든다.

하나는 더 큰 값의 인덱스들이 저장된 모노토닉 데크,maxima라 하겠다.

하나는 더 작은 값의 인덱스들이 저장된 모노토닉 데크, minima라 하겠다.

 

r을 두 데크의 맨 뒤에 넣어야 한다.

maxima의 뒤부터, nums[r]보다 작거나 같은 인덱스들은 모두 빼주고, 맨 뒤에 r을 넣는다.

minima의 뒤부터, nums[r]보다 크거나 같은 인덱스들은 모두 빼주고, 맨 뒤에 r을 넣는다.

이러면 maxima의 앞쪽에는 더 큰 값들이 유지되고, minima의 앞쪽에는 더 작은 값들이 저장되는 형태가 유지된다.

 

이제, 부분배열 범위의 최대, 최소를 구할 수 있다.

이 차가 2를 넘는 동안, 왼쪽 포인터를 당겨서 윈도우를 줄여야 한다.

l을 당겨오면서, 각각의 데크에서 l보다 작거나 같다면 제거한다.

 

이제, [l, r]의 범위는 조건을 만족하는 범위가 된다. 이제 개수를 누적해보자.

그러나, [l, r-1]까지는 이미 개수가 누적되어있다.

중복을 방지하기 위해, 현재 윈도우의 길이만큼만 더한다. 이는 l을 줄인 부분배열에 r을 추가하고 생긴 새로운 부분배열의 개수이다.

(기존 부분배열 조합들의 개수 + [r]만 있는 1가지)

 

최종 답을 반환하면 된다.

 

코드

C++

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        int l = 0;
        deque<int> maxima;
        deque<int> minima;

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

            while (!minima.empty() && nums[minima.back()] >= nums[r])
                minima.pop_back();
            minima.push_back(r);

            while (nums[maxima.front()] - nums[minima.front()] > 2) {
                if (maxima.front() <= l) maxima.pop_front();
                if (minima.front() <= l) minima.pop_front();
                ++l;
            }

            ans += (r - l + 1);
        }

        return ans;
    }
};