Check if an Array Is Sorted

Posortowana tablica to taka, której sortowanie niczego by nie zmieniło. Zrób więc kopię nums, posortuj ją i sprawdź, czy zgadza się z oryginałem element po elemencie. Jeśli wszystkie elementy są zgodne, nums było już uporządkowane.

Dla [2, 5, 4, 9] posortowana kopia to [2, 4, 5, 9]. Na pozycji 1 w oryginale znajduje się 5, a w kopii 4, więc odpowiedzią jest false. Dla [1, 3, 3, 7] kopia jest identyczna z oryginałem, a odpowiedzią jest true.

To poprawne rozwiązanie, ale robi więcej, niż wymaga zadanie. Sortowanie ma złożoność O(n log n), czyli około 6 × 10^4 porównań dla 5000 liczb, a utworzenie kopii wymaga O(n) pamięci. Ponadto zawsze odczytuje całą tablicę, nawet jeśli już pierwsza para elementów jest nieuporządkowana.

Nie musisz znać posortowanej wersji, aby stwierdzić, czy tablica jest posortowana. Tablica jest uporządkowana niemalejąco dokładnie wtedy, gdy każdy element jest mniejszy lub równy elementowi znajdującemu się bezpośrednio po nim. Ponieważ relacja ≤ jest przechodnia (a ≤ b i b ≤ c oznaczają a ≤ c), sprawdzenie n-1 sąsiednich par obejmuje każdą parę pozycji.

Przejdź przez i od 1 do n-1 i porównaj nums[i-1] z nums[i]. W przypadku [2, 5, 4, 9] para (2, 5) jest poprawna, a para (5, 4) oznacza spadek, więc od razu zwracasz false, nie sprawdzając 9. Równe sąsiednie elementy są poprawne, ponieważ tylko warunek > oznacza błąd.

Każda para jest porównywana raz, więc złożoność czasowa wynosi O(n), a jedyną dodatkową pamięcią jest indeks pętli, O(1). Porównuj te dwie wartości bezpośrednio, zamiast je odejmować: przy wartościach do 10^9 różnica może przekroczyć zakres 32-bitowej liczby całkowitej.