Задача. Количество подмассивов, в которых максимальный элемент встречается не менее K раз
Задача. Дан целочисленный массив nums и положительное целое число k.
Необходимо вернить количество подмассивов, в которых максимальный элемент массива nums встречается в этом подмассиве не менее k раз.
Справка: подмассив - это последовательность элементов внутри массива.
Входные данные: размер массива от 1 до 10^5, значения элементов массива от 1 до 10^5. K - от 1 до 10^5.
[1,3,2,3,3], k = 2
Output: 6
Пояснение: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3], [3,3]
Разбор
В данной задаче нам нужны подмассивы и частота максимального элемента, поэтому метод скользящего окна идеально подойдет для решения.
Напомним, что метод скользящего окна управляется двумя указателями, один указывает начало, другой конец окна.
При обходе массива мы будем следить частоту максимального элемента. Также при достижении частоты с параметром K, мы запустим дополнительный цикл для поиска всех подмассивов, у ктр частота максимального элемента равна K. Внутри этого цикла если мы встретим максимальный элемент, мы уменьшим скользящее окно.
Смотрите детали реализации ниже.
Реализация
static long CountSubArrays(int[] nums, int k) {
int len = nums.Length;
int max = nums.Max(); int start = 0;
long res = 0; int maxCountInWindow = 0;
for (int end = 0; end < len; end++) {
if (nums[end] == max)
maxCountInWindow++;
while (k == maxCountInWindow) {
if (nums[start] == max) {
maxCountInWindow--;
}
start++;
}
res += start;
}
return res;
}https://gist.github.com/unilecs/d9df24e45bd8752fbd03a24512e2ec19