首页算法

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

# 滑动窗口 + 计数排序

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int i = 0;
        int[] arr = new int[101];
        // 先添加 k - 1 个数
        while (i < k - 1) {
            arr[nums[i++] + 50]++;
        }
        int[] ans = new int[n - k + 1];
        for (; i < n; i++) {
            arr[nums[i] + 50]++;
            // 计算第 x 个负数
            //x 左边有 x - 1 个数
            int cur = 50;
            int cnt = 0;
            for (int j = 0; cnt < x && j < 50; j++) {
                if (arr[j] > 0) {
                    cnt += arr[j];
                    cur = j;
                }
            }
            //cnt > x 说明第 x 个元素有多个
            ans[i - k + 1] = cnt >= x ? cur - 50 : 0;
            // 移除左边的元素
            arr[nums[i - k + 1] + 50]--;
        }
        return ans;
    }
}

# 复杂度分析

  • 时间复杂度：O(n2)O(n^2)，其中 nn 为 numsnums 的长度
  • 空间复杂度：O(n)O(n)

# 滑动窗口 + 平衡树

为什么采用平衡树而不采用堆，由于窗口滑动的过程中要删除元素，若采用堆还需要懒删除。

采用两个堆： x 及其左边采用倒序平衡树 minTree ， x 右边采用正序平衡树 maxTree

对于要进入窗口的元素 r ，以及要移除窗口的元素 l

l <= x ，删除 minTree 中 l

  • r <= x ，加入 minTree
  • r > x ，加入 maxTree 。将 maxTree 的最小元素放入 minTree

l > x ，删除 maxTree 中 l

  • r <= x ，加入 minTree 。将 minTree 的最大元素放入 maxTree
  • r > x ，加入 maxTree
class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        // 会有重复元素
        TreeMap<Integer, Integer> maxTree = new TreeMap<>();
        TreeMap<Integer, Integer> minTree = new TreeMap<>((o1, o2) -> o2 - o1);
        // 初始化平衡树
        for (int i = 0; i < k; i++) {
            maxTree.put(nums[i], maxTree.getOrDefault(nums[i], 0) + 1);
        }
        // 将 x 及之前的元素放入 x 左边
        for (int i = 0; i < x; ) {
            Map.Entry<Integer, Integer> entry = maxTree.pollFirstEntry();
            minTree.put(entry.getKey(), entry.getValue());
            i += entry.getValue();
            // -22 0 0 46 47, k = 5, x = 2
            // 说明 minTree 多了元素
            if (i > x) {
                minTree.put(entry.getKey(), entry.getValue() - (i - x));
                maxTree.put(entry.getKey(), i - x);
            }
        }
        // 获取第 x 个元素 v
        int v = minTree.firstKey();
        ans[0] = Math.min(v, 0);
        // 滑动窗口
        for (int i = k; i < n; i++) {
            int l = nums[i - k];
            int r = nums[i];
            if (l <= v) {
                // 删除 minRtree 中 l
                if (minTree.get(l) == 1) {
                    minTree.remove(l);
                } else {
                    minTree.put(l, minTree.get(l) - 1);
                }
                if (r <= v) {
                    minTree.put(r, minTree.getOrDefault(r, 0) + 1);
                } else {
                    maxTree.put(r, maxTree.getOrDefault(r, 0) + 1);
                    // 将 maxTree 的最小元素放入 minTree
                    Map.Entry<Integer, Integer> entry = maxTree.firstEntry();
                    if (entry.getValue() == 1) {
                        maxTree.pollFirstEntry();
                    } else {
                        maxTree.put(entry.getKey(), entry.getValue() - 1);
                    }
                    minTree.put(entry.getKey(), minTree.getOrDefault(entry.getKey(), 0) + 1);
                }
            } else {
                if (maxTree.get(l) == 1) {
                    maxTree.remove(l);
                } else {
                    maxTree.put(l, maxTree.get(l) - 1);
                }
                if (r <= v) {
                    minTree.put(r, minTree.getOrDefault(r, 0) + 1);
                    // 将 minTree 的最小元素放入 maxTree
                    Map.Entry<Integer, Integer> entry = minTree.firstEntry();
                    if (entry.getValue() == 1) {
                        minTree.pollFirstEntry();
                    } else {
                        minTree.put(entry.getKey(), entry.getValue() - 1);
                    }
                    maxTree.put(entry.getKey(), maxTree.getOrDefault(entry.getKey(), 0) + 1);
                } else {
                    maxTree.put(r, maxTree.getOrDefault(r, 0) + 1);
                }
            }
            v = minTree.firstKey();
            ans[i - k + 1] = Math.min(v, 0);
        }
        return ans;
    }
}
# 复杂度分析


    

  • 时间复杂度：O(nlogn)O(nlogn)，其中 nn 为 numsnums 的长度
    • 

  • 空间复杂度：O(n)O(n)
    •