Algorithms training - 2023 12月 Training plan

2023 12月 Training plan

今个月的重点:

  • 滑动窗口
  • 递归
  • DP

滑动窗口

统计最大元素出现至少 K 次的子数组
给你一个整数数组 nums 和一个 正整数 k 。
请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。
子数组是数组中的一个连续元素序列。

示例 1：
输入：nums = [1,3,2,3,3], k = 2
输出：6
解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3]。

思路: 首先找到nums中的最大元素mx, 我们要统计子数组的个数可以考虑滑动窗口算法。
设置左右指针 l 和 r, 于是我们枚举右指针 r 继续滑动, 途中我们要维护一个 cnt_max 来记录该窗口中最大元素出现的次数。
于是我们可以在 cnt_max == k 移动左指针 l, 目的知道 cnt_max != k 为止, 此时 [l, r] 有 k - 1 个最大元素并且 nums[l - 1]一定是最大元素, 于是对答案的贡献就为 l 了。(因为区间运算 l - 1 - 0 + 1, 子数组数量相当于从l - 1到0的每个元素开始到当前区间结束, 也就是 l 次。) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    using ll = long long;
    ll countSubarrays(vector<int>& nums, int k) {
        ll ans = 0;
        int l = 0, r = 0;
        int mx = *max_element(nums.begin(), nums.end());
        int n = nums.size();
        int cnt_max = 0;
        while (r < n) {
            if (nums[r] == mx) cnt_max++;
            while (cnt_max == k) {
                if (nums[l] == mx) {
                    cnt_max--;
                }
                l++;
            }
            ans += (l - 1) - 0 + 1;
            r++;
        }

        return ans;   
    }
};

递归

DP