[LeetCode] 3254. Find the Power of K-Size Subarrays I

https://leetcode.com/problems/find-the-power-of-k-size-subarrays-i/description/?envType=daily-question&envId=2024-11-16

leetcode - Find the Power of K-Size Subarrays I

문제 유형: 슬라이딩 윈도우

문제 난이도: Medium

 

문제

You are given an array of integers nums of length n and a positive integer k.

The power of an array is defined as:

• Its maximum element if all of its elements are consecutive and sorted in ascending order.
• -1 otherwise.

You need to find the power of all subarrays of nums of size k.

Return an integer array results of size n - k + 1, where results[i] is the power of nums[i..(i + k - 1)].

 

정수 배열을 n길이만큼 받고, 양의정수 k를 받는다.

array의 power는 다음과 같이 정의된다:

만약 요소들이 연속적이고 오름차순 정렬되어있다면, 가장 큰 요소

아니면 -1.

 

모든 k짜리 크기의 부분배열의 값들을 배열에 담아서 구하시오.

즉, results[i] = nums[i...(i+k-1)]의 power가 되어야 합니다.

 

풀이

이전 수를 저장하는 lastnum, 연속된 스트릭을 저장하는 streak변수를 만든다.

앞의 k-1개의 요소들을 창으로 밀면서, 스트릭을 계산한다.

 

이후부터 하나씩 읽으면서 스트릭을 갱신하고, 만약 스트릭이 k보다 크다면 현재 인덱스의 수를, 아니라면 -1을 정답 배열에 추가한다.

 

코드

C++

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;

        int streak = 1;
        int lastnum = nums[0];
        for(int i = 1; i < k-1; ++i) {
            if(lastnum+1 == nums[i]) streak++;
            else streak = 1;
            lastnum = nums[i];
        }

        for(int i = k-1; i < n; ++i) {
            if(lastnum+1 == nums[i]) streak++;
            else streak = 1;
            lastnum = nums[i];
            if(streak >= k) ans.push_back(lastnum);
            else ans.push_back(-1);
        }

        return ans;
    }
};