What is the core pattern in Sliding Subarray Beauty?

It combines array scanning with a hash or frequency map to track negative numbers within each sliding window.

How do I find the xth smallest negative efficiently?

Maintain a frequency array or hash for negatives and accumulate counts to locate the xth smallest without full sorting.

Can this approach handle large arrays?

Yes, using a fixed-size frequency array and sliding window updates, it works efficiently for arrays up to length 10^5.

What happens if a window has fewer than x negative numbers?

Return 0 for that window, as defined in the problem statement.

Why is the negative frequency map better than sorting each window?

It reduces time complexity from O(k log k) per window to O(1) per update using bounded counts, crucial for large n.

#2653

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

滑动子数组的美丽值

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的美丽值。一个子数组的美丽值定义为：如果子数组中第 x 小整数是负数，那么美丽值为第 x 小的数，否则美丽值为 0 。请你返回一个包含 n - k + 1 个整数的数组，依次表示数组中从第一个下标开始，…

数组哈希表滑动窗口

题目描述

给你一个长度为 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

lightbulb

解题思路

方法一：滑动窗口

我们注意到，数组 $nums$ 中元素的范围为 $[-50,50]$ ，因此，我们可以用一个数组长度为 $101$ 的数组 $cnt$ 统计 $[-50,50]$ 中每个数出现的次数。由于负数的存在，我们可以将每个数加上 $50$ ，使得每个数都变成非负数，这样就可以用数组 $cnt$ 统计每个数出现的次数了。

接下来，我们遍历数组 $nums$ ，维护一个长度为 $k$ 的滑动窗口，窗口中所有元素出现的次记数录在数组 $cnt$ 中，然后我们遍历数组 $cnt$ ，找到第 $x$ 小的负数，即为当前滑动窗口的美丽值。如果不存在第 $x$ 小的负数，那么美丽值为 $0$ 。

时间复杂度 $O(n \times 50)$ ，空间复杂度 $O(100)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        sl = SortedList(nums[:k])
        ans = [sl[x - 1] if sl[x - 1] < 0 else 0]
        for i in range(k, len(nums)):
            sl.remove(nums[i - k])
            sl.add(nums[i])
            ans.append(sl[x - 1] if sl[x - 1] < 0 else 0)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n * 51) using the fixed-count approach per window, which is effectively O(n). Space complexity is O(51) for the negative frequency array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask for maintaining a frequency of negative numbers efficiently.
question_mark
Check if candidate recognizes the fixed bound optimization for nums[i].
question_mark
Expect sliding window plus hash or array count discussion.

warning

常见陷阱

外企场景

error
Not updating the counts correctly when the window slides.
error
Returning the xth smallest across all numbers instead of negatives only.
error
Using a full sort of each window instead of frequency-based lookup.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the maximum negative number in each sliding window of size k.
arrow_right_alt
Return the sum of x smallest negative numbers for each subarray.
arrow_right_alt
Find the xth largest negative number instead of smallest in each window.

help

常见问题

外企场景

继续练习

#2747 统计没有收到请求的服务器数目 #2537 统计好子数组的数目 #2781 最长合法子字符串的长度