Блог

Дан массив A, содержащий n целых чисел. Задача состоит в том, чтобы проверить, является ли массив монотонным или нет. Массив является монотонным, если он либо монотонно увеличивается, либо монотонен decreasing.
An массив A монотонно увеличивается, если для всех i <= j, A[i] <= A[j]. Массив A монотонно уменьшается, если для всех i <= j, A[i] >= A[j]>.
Возвращает “True”, если данный массив A монотонен, иначе возвращает “False” (без кавычек).

Примеры:

Input : 6 5 4 4
Output : true

Input : 5 15 20 10
Output : false

Подход:

Массив является монотонный если и только если это так монотонное увеличение, или монотонное уменьшение. С p и q подразумевает p. Поэтому нам нужно только проверить соседние элементы, чтобы определить, является ли массив монотонно увеличивающимся (или уменьшающимся) соответственно. Мы можем проверить каждое из этих свойств за один проход.
Чтобы проверить, является ли массив A монотонное увеличение, мы проверим A[i] <= A[i+1] для всех я индексирую от 0 до len(A)-2. Аналогичным образом мы можем проверить наличие монотонное уменьшение где A[i] >= A[i+1] для всех я индексирую от 0 до len(A)-2.
Примечание: Массив с один элемент можно считать, что это и то, и другое монотонное увеличение или уменьшение, следовательно, возвращает “Правда«.

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

# Python3 program to find sum in Nth group

# Check if given array is Monotonic
def isMonotonic(A):

	return (all(A[i] <= A[i + 1] for i in range(len(A) - 1)) or
			all(A[i] >= A[i + 1] for i in range(len(A) - 1)))

# Driver program
A = [6, 5, 4, 4]

# Print required result
print(isMonotonic(A))

# This code is written by
# Sanjit_Prasad

Выход:

True

Временная Сложность: O(N), где N-длина массива.