Medium

题目描述

给定一个包含 n 个整数的整数数组 nums，找到每个大小为 k 的子数组的美丽值。

子数组的美丽值是子数组中第 x 小的负整数（如果它是负数），如果负整数少于 x 个则为 0。

返回一个包含 n - k + 1 个整数的整数数组，表示从数组第一个索引开始按顺序的子数组的美丽值。

子数组是数组中连续的非空元素序列。

示例 1：

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

示例 2：

输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：有 4 个大小为 k = 2 的子数组。
对于 [-1, -2]，第 2 小的负整数是 -1。
对于 [-2, -3]，第 2 小的负整数是 -2。
对于 [-3, -4]，第 2 小的负整数是 -3。
对于 [-4, -5]，第 2 小的负整数是 -4。

示例 3：

输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：有 5 个大小为 k = 2 的子数组。
对于 [-3, 1]，第 1 小的负整数是 -3。
对于 [1, 2]，没有负整数，所以美丽值是 0。
对于 [2, -3]，第 1 小的负整数是 -3。
对于 [-3, 0]，第 1 小的负整数是 -3。
对于 [0, -3]，第 1 小的负整数是 -3。

约束条件：

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

解题思路

这是一个典型的滑动窗口问题，核心是维护窗口内负数的频率分布。

思路分析：

观察到数组元素范围在 [-50, 50]，可以利用这个特点进行优化。我们需要：

  1. 频率统计：使用数组记录当前窗口内每个负数的出现次数
  2. 滑动窗口：移动窗口时，动态更新频率统计
  3. 查找第x小负数：从最小负数开始遍历频率数组，累计计数直到达到第x个

具体算法：

  1. 建立一个频率数组 freq，索引对应负数值（-50到-1映射到索引0到49）
  2. 初始化第一个窗口的频率统计
  3. 对每个窗口位置：
    • 查找第x小的负数：从-50开始遍历，累计频次直到达到x
    • 滑动窗口：移除左边元素，添加右边元素
  4. 如果负数个数不足x个，返回0

这种方法的优势是利用了数值范围小的特点，避免了复杂的数据结构，时间复杂度为O(n)。

推荐解法：频率数组 + 滑动窗口，时间复杂度最优。

代码实现

class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        vector<int> freq(50, 0); // 频率数组，索引0对应-50，索引49对应-1
        vector<int> result;
        int n = nums.size();
        
        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            if (nums[i] < 0) {
                freq[-nums[i] - 1]++;
            }
        }
        
        // 查找第一个窗口的美丽值
        result.push_back(findXthSmallest(freq, x));
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            // 移除左边元素
            if (nums[i - k] < 0) {
                freq[-nums[i - k] - 1]--;
            }
            // 添加右边元素
            if (nums[i] < 0) {
                freq[-nums[i] - 1]++;
            }
            // 查找当前窗口的美丽值
            result.push_back(findXthSmallest(freq, x));
        }
        
        return result;
    }
    
private:
    int findXthSmallest(const vector<int>& freq, int x) {
        int count = 0;
        for (int i = 49; i >= 0; i--) { // 从-1到-50遍历
            count += freq[i];
            if (count >= x) {
                return -(i + 1);
            }
        }
        return 0; // 负数不足x个
    }
};

class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        freq = [0] * 50  # 频率数组，索引0对应-50，索引49对应-1
        result = []
        n = len(nums)
        
        # 初始化第一个窗口
        for i in range(k):
            if nums[i] < 0:
                freq[-nums[i] - 1] += 1
        
        # 查找第一个窗口的美丽值
        result.append(self.find_xth_smallest(freq, x))
        
        # 滑动窗口
        for i in range(k, n):
            # 移除左边元素
            if nums[i - k] < 0:
                freq[-nums[i - k] - 1] -= 1
            # 添加右边元素
            if nums[i] < 0:
                freq[-nums[i] - 1] += 1
            # 查找当前窗口的美丽值
            result.append(self.find_xth_smallest(freq, x))
        
        return result
    
    def find_xth_smallest(self, freq, x):
        count = 0
        for i in range(49, -1, -1):  # 从-1到-50遍历
            count += freq[i]
            if count >= x:
                return -(i + 1)
        return 0  # 负数不足x个

public class Solution {
    public int[] GetSubarrayBeauty(int[] nums, int k, int x) {
        int[] freq = new int[50]; // 频率数组，索引0对应-50，索引49对应-1
        List<int> result = new List<int>();
        int n = nums.Length;
        
        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            if (nums[i] < 0) {
                freq[-nums[i] - 1]++;
            }
        }
        
        // 查找第一个窗口的美丽值
        result.Add(FindXthSmallest(freq, x));
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            // 移除左边元素
            if (nums[i - k] < 0) {
                freq[-nums[i - k] - 1]--;
            }
            // 添加右边元素
            if (nums[i] < 0) {
                freq[-nums[i] - 1]++;
            }
            // 查找当前窗口的美丽值
            result.Add(FindXthSmallest(freq, x));
        }
        
        return result.ToArray();
    }
    
    private int FindXthSmallest(int[] freq, int x) {
        int count = 0;
        for (int i = 49; i >= 0; i--) { // 从-1到-50遍历
            count += freq[i];
            if (count >= x) {
                return -(i + 1);
            }
        }
        return 0; // 负数不足x个
    }
}

var getSubarrayBeauty = function(nums, k, x) {
    const freq = new Array(50).fill(0); // 频率数组，索引0对应-50，索引49对应-1
    const result = [];
    const n = nums.length;
    
    // 初始化第一个窗口
    for (let i = 0; i < k; i++) {
        if (nums[i] < 0) {
            freq[-nums[i] - 1]++;
        }
    }
    
    // 查找第一个窗口的美丽值
    result.push(findXthSmallest(freq, x));
    
    // 滑动窗口
    for (let i = k; i < n; i++) {
        // 移除左边元素
        if (nums[i - k] < 0) {
            freq[-nums[i - k] - 1]--;
        }
        // 添加右边元素
        if (nums[i] < 0) {
            freq[-nums[i] - 1]++;
        }
        // 查找当前窗口的美丽值
        result.push(findXthSmallest(freq, x));
    }
    
    return result;
    
    function findXthSmallest(freq, x) {
        let count = 0;
        for (let i = 49; i >= 0; i--) { // 从-1到-50遍历
            count += freq[i];
            if (count >= x) {
                return -(i + 1);
            }
        }
        return 0; // 负数不足x个
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

详细分析：

  • 时间复杂度：O(n)，其中 n 是数组长度。虽然内层循环最多执行50次，但这是常数，总体仍为线性时间复杂度
  • 空间复杂度：O(1)，使用固定大小的频率数组（50个元素），不随输入规模变化