第 375 场力扣周赛

统计最大元素出现至少 K 次的子数组

题目

输入长度为 \(n\) 的数组 \(a\) 和整数 \(k\)，输出满足 \(\max(a)\) 至少出现 \(k\) 次的子数组的数目。

数据范围：\(1\leq n\leq 10^{5}\)，\(1\leq k\leq 10^{5}\)。

思路

首先计算出最大值，然后将所有最大值的下标放入列表 \(l\) 中，最后枚举右端点即可。假设列表的长度为 \(m\)，当前枚举到 \(i\)，当 \(i<m-1\) 时，区间 \([l[i],l[i+1]-1]\) 范围内的右端点都对应 \(l[i-k+1]+1\) 数量的左端点，将它们相乘加入答案。特别的，当 \(i=m-1\) 时，取区间 \([l[i],n-1]\)。PS：也可以滑动窗口，使窗口内只包含 \(k-1\) 个最大值，这样计算答案的空间复杂度为 \(O(1)\)。

统计好分割方案的数目

题目

输入长度为 \(n\) 的数组 \(a\)，输出将数组分割为若干不相交子数组的方案数。不相交表示子数组之间没有相同的元素，答案对 \(10^{9}+7\) 取余。

数据范围：\(1\leq n\leq 10^{5}\)。

思路

因为要求子数组之间没有相同元素，那么相同元素必定只会出现在一个子数组中，首先统计每个元素的最小和最大下标，这两个下标构成的区间是不可分割的。然后将所有不可分割的区间进行合并，最后剩余的区间数假设为 \(m\)，那么就会有 \(2^{m-1}\) 种分割方案（因为 \(m\) 个区间有 \(m-1\) 个分割位置，每个分割位置有分割或者不分割两种状态）。PS：① 可以边计数边做乘法，不使用快速幂；② 可以只统计最大下标，然后遍历数组时维护最大下标的最大值，如果当前下标等于该值，那么就可以做一次分割。（代码）