Найдите индексы, имеющие не менее K невозрастающих элементов до и K неубывающих элементов после них.

Учитывая массив arr[] размера N и целое число K , задача состоит в том, чтобы найти все индексы в данном массиве, имеющие не менее K невозрастающих элементов до и K неубывающих элементов после них.

Примеры:

Input: arr[] = {1, 1, 1, 1, 1}, K = 0
Output: 0 1 2 3 4
Explanation: Since K equals 0, every index satisfies the condition.

Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 2
Output: -1
Explanation: No index has 2 non-increasing before it and 2 non-decreasing elements after it.

Подход: решение можно найти, используя концепцию массива префиксов и суффиксов. Выполните шаги, указанные ниже:

1. Сформируйте массив prefix[] , где prefix[i] представляет количество элементов до i , которые подчиняются невозрастающему порядку.
2. Сформируйте массив suffix[] , где suffix[i] представляет количество элементов после i , которые подчиняются неубывающему порядку.
3. Теперь в ответ должны быть включены только те индексы, для которых префикс [i] и суффикс [i] больше или равны K .

Ниже приведена реализация описанного выше подхода.

Сложность времени: НА)
Вспомогательное пространство: O(N), поскольку занято N дополнительного пространства.