Проверить, является ли заданный массив монотонным

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

Дан массив arr[] , содержащий N целых чисел, задача состоит в том, чтобы проверить, является ли массив монотонным или нет (монотонный означает, что массив либо в порядке возрастания, либо в порядке убывания).

Примеры:

Input: arr[] = {1, 2, 2, 3}
Output: Yes
Explanation: Here 1 < 2 <= 2 < 3. 
The array is in increasing order. Therefore it is monotonic.

Input: arr[] =  {6, 5, 4, 3}
Output: Yes
Explanation: Here 6 > 5 > 4 > 3. 
The array is in decreasing order. So it is monotonic.

Input: arr[] = {1, 5, 2}
Output: No
Explanation: Here 1 < 5 > 2. The array is neither increasing nor decreasing. 
So the array is not monotonic

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

  • If for each i in range [0, N-2], arr[i] ≥  arr[i+1] the array is in decreasing order.
  • If for each i in range [0, N-2], arr[i] ≤ arr[i+1], the array is in increasing order.

Выполните следующие шаги, чтобы решить проблему:

  • Пройдите массив arr[] от i = 0 до N-2 и проверьте, увеличивается ли массив по порядку
  • Пройдите массив arr[] от i = 0 до N-2 и проверьте, уменьшается ли массив в порядке
  • Если ни одно из двух предыдущих не верно, то массив не является монотонным.

Ниже приведена реализация вышеуказанного подхода:

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

Другой подход: (JavaScript) В этом подходе будет использоваться метод массива JavaScript, названный Every() , и поэтому мы дополнительно проверим, используя этот метод, является ли переданный массив монотонным по своей природе или нет.

Выполните следующие шаги:

  • Пройдитесь по массиву, используя метод every() , и проверьте, меньше ли текущий элемент, чем предыдущий.
  • Точно так же снова, используя метод every() , а также с использованием логического оператора ИЛИ ( | | ), проверьте, больше ли текущий элемент, чем предыдущий элемент или нет.
  • Возвращает true, если обнаруживается возрастающая или убывающая последовательность.

Ниже приведена реализация вышеуказанного подхода:

Выход:

Is Monotonic ?: true
Is Monotonic ?: false
Is Monotonic ?: true

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