2653. Sliding Subarray Beauty
Given an integer array nums containing n integers, find the beauty of each subarray of size k.
The beauty of a subarray is the xth smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.
Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.
- A subarray is a contiguous non-empty sequence of elements within an array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution {
public:
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
map<int,int> freq;
int neg = 0;
auto insert = [&](int x) {
if(x < 0) neg += 1;
freq[x] += 1;
};
auto erase = [&](int x) {
if(x < 0) neg -= 1;
freq[x] -= 1;
if(freq[x] == 0) freq.erase(x);
};
for(int i = 0; i < k; i++) insert(nums[i]);
auto work = [&]() {
if(neg < x) return 0;
int now = x;
for(auto [k,v] : freq) {
now -= v;
if(now <= 0) return k;
}
return 0;
};
vector<int> res;
res.push_back(work());
for(int i = k; i < nums.size(); i++) {
insert(nums[i]);
erase(nums[i-k]);
res.push_back(work());
}
return res;
}
};
|
