滑动子数组的美丽值

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.

 

Example 1:

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.

Example 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. 

Example 3:

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.

 

Constraints:

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

import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 给定一个整数数组 nums 和两个整数 k 和 x, 使用 Java Stream API 求出每个长度为 k 的子数组的美丽值。
 * 美丽值定义为：如果子数组中第 x 小的整数是负数，则美丽值为该数；否则为 0。
 */
public class Solution {
    public int[] getBeautyValues(int[] nums, int k, int x) {
        return IntStream.rangeClosed(0, nums.length - k)
                .map(i -> Arrays.stream(nums, i, i + k)
                        .sorted()
                        .toArray()[x - 1])
                .map(value -> value < 0 ? value : 0)
                .toArray();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, -1, -3, -2, 3};
        int k = 3;
        int x = 2;
        System.out.println(Arrays.toString(sol.getBeautyValues(nums, k, x)));
    }
}

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

O(n)

O(1)