滑动子数组的美丽值

难度: Medium

给你一个长度为 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 <= 10⁵
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

Submission

运行时间: 375 ms

内存: 25.9 MB

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        d = [0 for _ in range(101)] #记录每个值有多少个
        for i in range(k): #先记录前k个值
            d[nums[i]] += 1
        res = []

        cnt = 0
        for a in range(-50,51):
            cnt += d[a]
            if cnt >= x: # 初始的第x小值a,cnt是小于等于a的数的个数
                break
        res.append(a if a < 0 else 0)

        for i in range(len(nums)-k):
            d[nums[i]] -= 1
            d[nums[i+k]] += 1 #除去离开的，增加新加入的
            cnt += int(nums[i+k] <= a) - int(nums[i] <= a) #更新cnt
            if cnt < x: # 第x小值大于a，则更新a和cnt
                while cnt < x:
                    a += 1
                    cnt += d[a]
            elif cnt - d[a] >= x: # 第x小值小于等于cnt对应值，则更新cnt和a
                while cnt - d[a] >= x:
                    cnt -= d[a]
                    a -= 1
            res.append(a if a < 0 else 0)
        return res

Explain

此题解使用滑动窗口和直接数组索引的方法来维护和更新子数组内元素的计数，从而实时获取子数组内第x小的值。初始化时，首先统计前k个元素的计数，然后寻找当前第x小的值。在随后的滑动窗口操作中，对每次滑动窗口的移动，都会调整计数数组，并重新确定第x小的值。如果新计算出的第x小的值是负数，则记录此值；如果不是，则记录0。此方法避免了对每个窗口内的所有元素进行排序，大大提高了效率。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        d = [0 for _ in range(101)] # 初始化计数数组, 索引从-50到50映射到0到100
        for i in range(k): # 统计初始k个元素的计数
            d[nums[i]] += 1
        res = []

        cnt = 0
        for a in range(-50,51): # 找到初始窗口中第x小的数
            cnt += d[a]
            if cnt >= x: # 当累积计数达到x时，确定a为第x小的数
                break
        res.append(a if a < 0 else 0) # 根据a是否为负数添加美丽值

        for i in range(len(nums)-k):
            d[nums[i]] -= 1 # 移出窗口的元素计数减1
            d[nums[i+k]] += 1 # 新进入窗口的元素计数加1
            cnt += int(nums[i+k] <= a) - int(nums[i] <= a) # 更新小于等于a的元素计数
            if cnt < x: # 如果计数小于x，需要向右调整a
                while cnt < x:
                    a += 1
                    cnt += d[a]
            elif cnt - d[a] >= x: # 如果计数大于等于x，需要向左调整a
                while cnt - d[a] >= x:
                    cnt -= d[a]
                    a -= 1
            res.append(a if a < 0 else 0) # 添加当前窗口的美丽值
        return res

Explore

题解中使用的计数数组d是基于nums数组中的元素只在[-50, 50]范围内的假设。如果nums中存在超出这个范围的值，则计数数组d无法正确地统计这些值，因此这种方法在该假设不成立时不适用。实际应用中需要根据数据的具体范围调整计数数组的大小和映射逻辑。

计数数组的大小为101是基于输入数组nums的值只在[-50, 50]之间这一假设。这样可以通过将值加50来直接映射到数组索引中。如果输入数组的范围是[-1000, 1000]，则需要调整数组大小为2001，并相应地调整索引映射（即值加1000映射到索引）。这种方法在调整后仍然适用，但需要更多的空间和适当的索引调整。

线性遍历计数数组的方式在最坏情况下需要遍历整个计数数组，其时间复杂度为O(n)，其中n是计数数组的长度。当计数数组很大时，这种方法可能会较慢。一个更优的查找方法是使用平衡二叉搜索树或优先队列来维护元素的计数，这样可以更快地找到第x小的数。例如，使用红黑树或AVL树，可以在O(log n)时间内完成插入、删除和查找操作。

在滑动窗口的更新过程中，确实可能出现cnt计数错误的情况，特别是在元素频率的增减处理上。要确保计数的准确性，需要仔细处理每个元素进入和离开窗口时对计数数组的更新。此外，每次更新后，检查cnt的值是否与窗口内元素的总数相符，可以通过遍历计数数组验证，确保每次更新后cnt的值正确反映了第x小值的位置。