题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个整数数组，元素取值为[-50, 50]，按要求返回各子数组中的“美丽值”，要求子数组的长度为 k，而“美丽值”是其中第 x 小的负数，如果没有负数，则为 0.

思路分享

代码解答（强烈建议自行解答后再看）

  • 定长滑动窗口+穷举遍历
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
class Solution {
public:
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        const int BIAS = 50;
        vector<int> num_rec(2*BIAS+1, 0);
        

        // 先初始化 k-1 长度的窗口
        for (int i = 0; i < k-1; i++) {
            num_rec[nums[i]+BIAS]++;
        }

        // 开始滑动窗口
        int n = nums.size();
        vector<int> res(n-k+1, 0);
        for (int i = k-1; i < n; i++) {
            num_rec[nums[i]+BIAS]++;
            int negative = x;
            for (int j = 0; j < BIAS; j++) {
                negative -= num_rec[j];
                if (negative <= 0) {
                    //cout << j-BIAS << endl;
                    res[i-k+1] = j-BIAS;
                    break;
                }
            }
            num_rec[nums[i-k+1]+BIAS]--;
        }

        return res;
    }
};