Определить, образует ли данный массив долину или нет

Учитывая массив arr[] длины N , задача состоит в том, чтобы проверить, образует ли данный массив долину или нет. Массив называется долиной, если существует точка, до которой массив не возрастает, а затем увеличивается по своей природе. Формально обр[0] ≥ обр[1] ≥ . . . ≥ обр[i] ≤ обр[i+1] ≤ . . . ≤ arr[N-1] и arr[0] > arr[i] и arr[i] < arr[N-1] , где i — любой индекс в диапазоне [1, N-2] .

Примечание. Массив, состоящий только из одного элемента, также считается долиной.

Input: N = 6  arr[] = {5, 4, 4, 3, 2, 2}
Output: No

Not a valley

Input: N = 8  arr[] = {5, 4, 4, 3, 4, 4, 5, 6}
Output: Yes

valley representing given input

Input: N = 5  arr[] = {4, 5, 5, 6, 4}
Output: No

array doesn’t form a valley

Подход: Задача может быть решена с помощью линейной итерации, основанной на следующей идее:

Find any index i, such that all the elements before that are in non-increasing order and after that all the elements are in non-decreasing order.

Следуйте инструкциям, чтобы решить проблему:

• Перейдите от начала к индексу (скажем, idx ), где текущий элемент становится больше, чем предыдущий.
• От этого индекса пройдите до конца и проверьте, находятся ли они в неубывающем порядке.
• Наконец, проверьте, меньше ли arr[idx-1] значений arr[0] и arr[N-1] .
• Если вышеуказанные условия выполнены, верните «Да». В противном случае массив не образует долину.

Ниже приведен код для обсуждаемого подхода:

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Найдите, имеет ли заданный массив форму горы или нет