Medium - Sliding Subarray Beauty

https://leetcode.com/problems/sliding-subarray-beauty/description/

Sliding Subarray Beauty - LeetCode

문제 설명

Given an integer array nums containing n integers, find the beauty of each subarray of size k.

The beauty of a subarray is the xth smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.

Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.

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

Constraints:

• n == nums.length 
• 1 <= n <= 10 ** 5
• 1 <= k <= n
• 1 <= x <= k 
• -50 <= nums[i] <= 50 

예시

Input: nums = [1,-1,-3,-2,3], k = 3, x = 2
Output: [-1,-2,-2]
Explanation: There are 3 subarrays with size k = 3. 
The first subarray is [1, -1, -3] and the 2nd smallest negative integer is -1. 
The second subarray is [-1, -3, -2] and the 2nd smallest negative integer is -2. 
The third subarray is [-3, -2, 3] and the 2nd smallest negative integer is -2.

Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
Output: [-1,-2,-3,-4]
Explanation: There are 4 subarrays with size k = 2.
For [-1, -2], the 2nd smallest negative integer is -1.
For [-2, -3], the 2nd smallest negative integer is -2.
For [-3, -4], the 2nd smallest negative integer is -3.
For [-4, -5], the 2nd smallest negative integer is -4.

Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
Output: [-3,0,-3,-3,-3]
Explanation: There are 5 subarrays with size k = 2.
For [-3, 1], the 1st smallest negative integer is -3.
For [1, 2], there is no negative integer so the beauty is 0.
For [2, -3], the 1st smallest negative integer is -3.
For [-3, 0], the 1st smallest negative integer is -3.
For [0, -3], the 1st smallest negative integer is -3.

풀이

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        length = len(nums)
        ret = [0, ] * (length - k + 1)

        negatives = [0, ] * 50
        
        for i in range(length):
            if nums[i] < 0:
                negatives[50+nums[i]] += 1
            
            if i - k >= 0 and nums[i-k] < 0:
                negatives[50+nums[i-k]] -= 1

            if i >= k - 1:
                cnt = 0
                for j in range(50):
                    cnt += negatives[j]
                    if cnt >= x:
                        ret[i - k + 1] = j - 50
                        break
        
        return ret

처음엔 Priority Queue, Heap을 사용해서 N번째가 아니면 다시 Put하는 방식을 생각했는데, time limit exceeded 에러가 난다.

다행히 목표가 되는 값의 범위를 -50 ~ -1 로 제한하는 Constraint가 있어서 Map 형식으로 풀이 할 수 있다.

이게 문제의 의도인지 확신은 없다.