本文涉及的基础知识点

C++算法：滑动窗口及双指针总结
C++堆(优先队列)

LeetCode2653. 滑动子数组的美丽值

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

滑动窗口

第x小，可以用对顶堆来实现。本题nums[i]的范围比较小，可以直接统计。将nums[i]+=50。则nums[i]$\in$[0,100]
cnt[i]记录滑动窗口内i的数量。
cnt[0…j]之和 >= x，且j最小便是滑动窗口第x小。则当前滑动窗口的美丽值是min(0,j-50)。

代码

核心代码

class Solution {
		public:
			vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
				for (auto& n : nums) {
					n += 50;
				}
				int cnt[101] = { 0 };
				int i = 0;
				for (; i < k; i++) {
					cnt[nums[i]]++;
				}
				vector<int> res;
				auto DoRes = [&]() {
					for (int i = 0, sum = 0; ; i++) {
						sum += cnt[i];
						if (sum >= x) { res.emplace_back(min(0, i - 50)); return; }
					}					
				};
				DoRes();
				for (; i < nums.size(); i++) {
					cnt[nums[i]]++;
					cnt[nums[i - k]]--;
					DoRes();
				}
				return res;
			}
		};

代码测试

vector<int> nums;
		int k,  x;
		TEST_METHOD(TestMethod1)
		{
			nums = { 1 }, k = 1, x = 1;
			auto res = Solution().getSubarrayBeauty(nums, k, x);
			AssertEx({ 0}, res);
		}
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, -1, -3, -2, 3 }, k = 3, x = 2;
			auto res = Solution().getSubarrayBeauty(nums, k, x);
			AssertEx({ -1,-2,-2 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { -1, -2, -3, -4, -5 }, k = 2, x = 2;
			auto res = Solution().getSubarrayBeauty(nums, k, x);
			AssertEx({ -1,-2,-3,-4 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { -3, 1, 2, -3, 0, -3 }, k = 2, x = 1;
			auto res = Solution().getSubarrayBeauty(nums, k, x);
			AssertEx({ -3,0,-3,-3,-3 }, res);
		}