[Leetcode 3254번 문제] 3254. Find the Power of K-Size Subarrays I.

문제 상황

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)].

i 번째부터 i + k - 1까지의 요소가 주어진 배열 nums가 있고, power이라함은 증가수열일때 존재하는것.

입력

Constraints:

• 1 <= n == nums.length <= 500
• 1 <= nums[i] <= 10 ^ 5
• 1 <= k <= n

출력

nums배열이

과정

슬라이딩 윈도우처럼해서 기존의 윈도우의 모든 요소를 파악하는데 그걸 매번 k개가 되지않게 정보들을 잘 저장해놓는 방식으로 정리하려한다.

증가하는 수열이란걸 알아야함. 1번 요소부터 큐로 넣는것을 한다. 기준은 이전요소보다 내가 큰지

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        queue<int> q;
        vector<int> answer(nums.size() - k + 1, 0);
        if (k == 1)
        {
            return nums;
        }
        for (int i = 1; i < k; i++)
        {
            if (nums[i] <= nums[i - 1])
            {
                q.push(i);
            }
        }

        for (int i = k - 1; i < nums.size(); i++)
        {
            int tmp = 0;
            if (nums[i] <= nums[i - 1])
            {
                if (i != k - 1)
                    q.push(i);
                tmp = -1;
            }
            else
            {
                if (q.empty())
                {
                    tmp = nums[i];
                }
                else
                {
                    tmp = -1;
                }
            }
            answer[i - k + 1] = tmp;
            if (q.front() == i - k + 2)
            {
                q.pop();
            }
        }
        return answer;
    }
};

일단 1차 틀림이 있었다. consecutive가 이전값과 1차이 나는걸 의미하는듯

알고리즘 개요도

알고리즘

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        queue<int> q;
        vector<int> answer(nums.size() - k + 1, 0);
        if (k == 1)
        {
            return nums;
        }
        for (int i = 1; i < k; i++)
        {
            if (nums[i] != nums[i - 1] + 1)
            {
                q.push(i);
            }
        }

        for (int i = k - 1; i < nums.size(); i++)
        {
            int tmp = 0;
            if (nums[i] != nums[i - 1] + 1)
            {
                if (i != k - 1)
                    q.push(i);
                tmp = -1;
            }
            else
            {
                if (q.empty())
                {
                    tmp = nums[i];
                }
                else
                {
                    tmp = -1;
                }
            }
            answer[i - k + 1] = tmp;
            if (q.front() == i - k + 2)
            {
                q.pop();
            }
        }
        return answer;
    }
};

연속적인 것을 반영해서 해결