请用C++解决这个leetcode的问题:2653. 滑动子数组的美丽值 提示 中等 26 相关企业 给你一个长度为 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
时间: 2023-11-27 15:51:26 浏览: 120
zhanguohao#leetcode#LeetCode: 26. 删除排序数组中的重复项1
以下是C++的解法:
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> beautySum(vector<int>& nums, int k, int x) {
vector<int> res;
priority_queue<int> pq; // 大根堆,存储当前子数组中的负数
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i >= k) { // 超出窗口大小时,删除窗口中最左边的元素
if (!pq.empty() && nums[i - k] == -pq.top()) {
pq.pop();
}
}
if (nums[i] < 0) { // 如果当前元素是负数,加入大根堆
pq.push(-nums[i]);
}
if (i >= k - 1) { // 如果当前窗口大小达到k,计算子数组美丽值
if (pq.size() >= x) { // 如果当前子数组中负数的数量不少于x,取第x小的负数为美丽值
int beautiful = -pq.top();
res.push_back(beautiful);
} else { // 否则,当前子数组不存在第x小的负数,美丽值为0
res.push_back(0);
}
}
}
return res;
}
int main() {
vector<int> nums = {1, -1, -3, -2, 3};
int k = 3, x = 2;
vector<int> res = beautySum(nums, k, x);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
```
该算法的时间复杂度为 $O(n \log k)$,其中 $n$ 是数组长度,$k$ 是窗口大小。主要时间消耗在大根堆的插入和删除操作上。空间复杂度为 $O(k)$,即大根堆的大小。
阅读全文