【C++滑动窗口】2653. 滑动子数组的美丽值|1785

本文涉及的基础知识点

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);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功