Check if an Array Is Sorted

Отсортированный массив — это массив, который не изменится после сортировки. Поэтому создайте копию nums, отсортируйте её и проверьте, совпадает ли она с исходным массивом позиция за позицией. Если совпадают все позиции, значит, nums уже был упорядочен.

Для [2, 5, 4, 9] отсортированная копия будет [2, 4, 5, 9]. В позиции 1 в исходном массиве находится 5, а в копии — 4, поэтому ответ — false. Для [1, 3, 3, 7] копия идентична исходному массиву, поэтому ответ — true.

Это решение правильное, но оно делает больше, чем требуется в задаче. Сортировка требует O(n log n) операций — около 6 × 10^4 сравнений для 5000 чисел, а для копии требуется O(n) памяти. Кроме того, оно всегда просматривает весь массив, даже если уже первая пара не упорядочена.

Вам не нужна отсортированная версия, чтобы узнать, отсортирован ли массив. Массив упорядочен по неубыванию тогда и только тогда, когда каждый элемент не больше следующего за ним. Поскольку цепочки неравенств ≤ выполняются (a ≤ b и b ≤ c дают a ≤ c), проверки n-1 соседних пар достаточно, чтобы охватить все пары позиций.

Переберите i от 1 до n-1 и сравните nums[i-1] с nums[i]. Для [2, 5, 4, 9] пара (2, 5) подходит, а в паре (5, 4) порядок нарушается, поэтому сразу верните false, не проверяя 9. Равные соседние элементы подходят, потому что условие нарушается только при >.

Каждая пара сравнивается один раз, поэтому время выполнения составляет O(n), а единственная дополнительная память — это индекс цикла, O(1). Сравнивайте два значения напрямую, а не вычитайте одно из другого: при значениях до 10^9 разность может привести к переполнению 32-битного int.