2653-滑动子数组的美丽值

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为
0 。

请你返回一个包含 _ _n - k + 1 个整数的数组， 依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 **
美丽值** 。

• 子数组指的是数组中一段连续 非空 的元素序列。

示例 1：

**输入：** nums = [1,-1,-3,-2,3], k = 3, x = 2
**输出：** [-1,-2,-2]
**解释：** 总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

示例 2：

**输入：** nums = [-1,-2,-3,-4,-5], k = 2, x = 2
**输出：** [-1,-2,-3,-4]
**解释：** 总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

示例 3：

**输入：** nums = [-3,1,2,-3,0,-3], k = 2, x = 1
**输出：** [-3,0,-3,-3,-3]
**解释：** 总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= k <= n
• 1 <= x <= k
• -50 <= nums[i] <= 50

本题视频讲解

见【周赛 342】 第三题。

思路

滑动窗口。由于值域很小，所以借鉴计数排序，用一个 cnt 数组维护窗口内每个数的出现次数。然后遍历 cnt 去求第 x 小的数。

什么是第 x 小的数？

设它是 num，那么 <\textit{num 的数有 <x 个，\le\textit{num 的数有 \ge x 个，就说明 num 是第 x 小的数。

[sol1-Python3]

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        cnt = [0] * 101
        for num in nums[:k - 1]:  # 先往窗口内添加 k-1 个数
            cnt[num] += 1
        ans = [0] * (len(nums) - k + 1)
        for i, (in_, out) in enumerate(zip(nums[k - 1:], nums)):
            cnt[in_] += 1  # 进入窗口（保证窗口有恰好 k 个数）
            left = x
            for j in range(-50, 0):  # 暴力枚举负数范围 [-50,-1]
                left -= cnt[j]
                if left <= 0:  # 找到美丽值
                    ans[i] = j
                    break
            cnt[out] -= 1  # 离开窗口
        return ans

[sol1-Java]

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        final int BIAS = 50;
        var cnt = new int[BIAS * 2 + 1];
        int n = nums.length;
        for (int i = 0; i < k - 1; ++i) // 先往窗口内添加 k-1 个数
            ++cnt[nums[i] + BIAS];
        var ans = new int[n - k + 1];
        for (int i = k - 1; i < n; ++i) {
            ++cnt[nums[i] + BIAS]; // 进入窗口（保证窗口有恰好 k 个数）
            int left = x;
            for (int j = 0; j < BIAS; ++j) { // 暴力枚举负数范围 [-50,-1]
                left -= cnt[j];
                if (left <= 0) { // 找到美丽值
                    ans[i - k + 1] = j - BIAS;
                    break;
                }
            }
            --cnt[nums[i - k + 1] + BIAS]; // 离开窗口
        }
        return ans;
    }
}

[sol1-C++]

class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int> &nums, int k, int x) {
        const int BIAS = 50;
        int cnt[BIAS * 2 + 1]{}, n = nums.size();
        for (int i = 0; i < k - 1; ++i) // 先往窗口内添加 k-1 个数
            ++cnt[nums[i] + BIAS];
        vector<int> ans(n - k + 1);
        for (int i = k - 1; i < n; ++i) {
            ++cnt[nums[i] + BIAS]; // 进入窗口（保证窗口有恰好 k 个数）
            int left = x;
            for (int j = 0; j < BIAS; ++j) { // 暴力枚举负数范围 [-50,-1]
                left -= cnt[j];
                if (left <= 0) { // 找到美丽值
                    ans[i - k + 1] = j - BIAS;
                    break;
                }
            }
            --cnt[nums[i - k + 1] + BIAS]; // 离开窗口
        }
        return ans;
    }
};

[sol1-Go]

func getSubarrayBeauty(nums []int, k, x int) []int {
	const bias = 50
	cnt := [bias*2 + 1]int{}
	for _, num := range nums[:k-1] { // 先往窗口内添加 k-1 个数
		cnt[num+bias]++
	}
	ans := make([]int, len(nums)-k+1)
	for i, num := range nums[k-1:] {
		cnt[num+bias]++ // 进入窗口（保证窗口有恰好 k 个数）
		left := x
		for j, c := range cnt[:bias] { // 暴力枚举负数范围 [-50,-1]
			left -= c
			if left <= 0 { // 找到美丽值
				ans[i] = j - bias
				break
			}
		}
		cnt[nums[i]+bias]-- // 离开窗口
	}
	return ans
}

复杂度分析

• 时间复杂度：\mathcal{O}(nU)，其中 n 为 nums 的长度，U=50。
• 空间复杂度：\mathcal{O}(U)。