Количество подмассивов с максимальным значением как K

Опубликовано: 22 Сентября, 2022

Дан массив arr[] из N целых чисел и целое число K . Задача состоит в том, чтобы найти количество подмассивов с максимальным значением, равным K.

Примеры:

Input: arr[ ] = {2, 1, 3, 4}, K = 3
Output: 3
Explanation: 
Sub-arrays with maximum value is equals K are { 2, 1, 3 }, { 1, 3 }, { 3 }, hence the answer is 3.

Input: arr[ ] = {1, 2, 3}, K = 1.
Output: 1

Подход: количество подмассивов в массиве arr[] равно количеству подмассивов с максимальным значением не более K минус количество подмассивов с максимальным значением не более K-1. См. здесь подсчет количества подмассивов с максимальным значением, превышающим K. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную, скажем, count1 как 0 , чтобы вычислить количество подмассивов с максимальным значением, не превышающим K-1.
  • Инициализируйте переменную, скажем, count2 как 0 , чтобы вычислить количество подмассивов с максимальным значением, не превышающим K.
  • Определите функцию, скажем, totalSubarrays(arr, N, K) для подсчета количества подмассивов с максимальным значением, не превышающим K , и выполните следующие шаги:
    • Инициализируйте переменную, скажем, как 0 , чтобы сохранить количество подмассивов с максимальным значением, не превышающим K.
    • Повторите в диапазоне [0, N-1] и выполните следующие шаги.
      • Если значение arr[i] больше K, увеличьте значение i на 1 и продолжите.
      • Инициализируйте переменную count как 0 , чтобы сохранить общее количество возможных подмассивов.
      • Повторяйте в диапазоне до тех пор, пока i не станет меньше N , а arr[i] не станет меньше K.
        • Увеличьте значение i и подсчитайте на 1.
      • Добавьте значение (count*(count+1))/2 к значению ans.
    • Возвращает значение ответа.
  • Подсчитайте количество подмассивов с максимальным значением не более K-1 , вызвав функцию totalSubarrays(arr, N, K-1) и сохранив в count1.
  • Подсчитайте количество подмассивов с максимальным значением не более K , вызвав функцию totalSubarrays(arr, N, K) и сохранив в count2.
  • Сохраните значение (count2 – count1) в конечном значении ans и распечатайте его.

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

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ