滑动子数组的魅力

问题陈述

给定一个包含 n 个整数的整数数组 nums，找出每个大小为 k 的子数组的美观度。

一个子数组的美观度是该子数组中第 x 个最小的负整数（如果存在），如果没有少于 x 个负整数，则为 0。

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

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

示例

输入: nums = [-1,-2,-3,-4,-5], k = 2, x = 2

输出 [-1,-2,-3,-4]

说明

• 对于给定的输入数组 nums = [-1, -2, -3, -4, -5]，子数组大小 k = 2 和目标值 x = 2，有 4 个大小为 2 的子数组。第一个子数组是 [-1, -2]，第二个最小的负整数是 -2。第二个子数组是 [-2, -3]，第二个最小的负整数是 -3。第三个子数组是 [-3, -4]，第二个最小的负整数是 -4。第四个子数组是 [-4, -5]，第二个最小的负整数是 -4。因此，输出是 [-1, -2, -3, -4]。

Java 实现

Java 暴力解法

输出

代码解释

• 该算法处理一个整数数组 nums，在其上滑动一个大小为 k 的窗口。对于每个窗口，它维护一个频率映射 map。当窗口滑动时，map 会更新，增加每个遇到的数字的计数并减少离开窗口的数字的计数。
• 使用 findMin 方法确定所需范围 x 内的最小值。结果被收集到一个列表中并转换为数组。这种方法在窗口穿过数组时有效地计算每个大小为 k 的子数组中的最小值，为每个窗口提供一个最小值数组。

时间复杂度

• 该算法的时间复杂度是 O(N)，其中 N 是输入数组 nums 的长度。该算法处理每个元素一次，并在滑动窗口操作期间维护一个恒定大小的频率映射。

空间复杂度

• 空间复杂度是 O(1)，因为频率映射的大小是恒定的，与输入大小无关。所需的额外空间与数组中数字的范围成比例，由 NUM_RANGE 限制。

缺点

• 该算法的缺点是它依赖于固定范围 (NUM_RANGE) 来表示数字。如果该范围远大于输入数组中数字的实际范围，可能会导致不必要的空间使用。

使用滑动窗口的 Java 方法

输出

代码解释

• 上述 Java 程序基于输入数组上的滑动窗口计算一个新数组。它使用 TreeMap 有效地维护当前窗口中元素的频率。主方法首先从用户那里获取数组的长度和元素，以及子数组的长度 (k) 和值 x。
• getSubarrayBeauty 方法初始化初始窗口的 TreeMap，计算初始结果，然后滑动窗口同时更新 TreeMap。结果数组存储每个窗口的第 k 个最小负元素。getKthSmallestNeg 辅助方法遍历 TreeMap 以查找第 k 个最小负元素。

时间复杂度

• 所提供解决方案的时间复杂度为 O(N log K)，其中 N 是输入数组的长度，K 是子数组的长度。这是因为 TreeMap 操作（put 和 remove）需要对数时间。

空间复杂度

• 空间复杂度为 O(K)，因为 TreeMap 在滑动窗口中最多存储 K 个不同的元素，其中 K 是子数组的长度。

此解决方案的优点

• 上述解决方案优于暴力方法的优点在于其使用 TreeMap 的优化方法。通过维护一个 TreeMap 来跟踪滑动窗口中元素的出现次数，该算法可以有效地更新和检索第 k 个最小负元素。
• 这消除了在每个子数组中重复搜索的需要，显著降低了时间复杂度。TreeMap 允许对数时间复杂度进行元素检索，与暴力方法相比，优化了整体性能，因为暴力方法由于重复计算而具有更高的时间复杂度。