Проверить, является ли заданный массив монотонным
Дан массив 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