Monetonic Array LeetCode шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Facebook
Array

Проблеманы шешу

«Монотонды массив» мәселесінде бізге массив берілген. Біздің міндетіміз массивтің а екенін тексеру монотонды массив немесе жоқ.

Монотонды массив - бұл элементтер өсу ретімен немесе кему ретімен сұрыпталатын массив. Егер массив өсу ретімен сұрыпталса, онда [] массиві үшін arr [i] <= arr [i + 1] болады. Азаю ретімен сұрыпталған массив үшін arr [i]> = arr [i + 1].

Функция массив монотонды болған кезде ғана true мәнін қайтаруы керек. Әйтпесе, жалған деп қайтарыңыз.

мысал

arr={1,2,4,5}
true

Түсіндіру:  Әр массив үшін берілген жиымда [i]

жақындау

Бұл мәселені шешу үшін монотонды массивтің не екенін түсіну өте маңызды.

монотонды массив - массив, егер массивтің индексі бойынша индекс нөмірі мен мәні арасында график салсақ, онда ол монотонды өсетін немесе кемитін график құрайды. Төмендегі суретте монотонды өсетін және кемитін график көрсетілген.

монотонды массивке арналған leetcode шешімі

Бұл мәселеге көзқарас сияқты, біз массивті айналып өтіп, оның [i] <= arr [i + 1] тексеру арқылы ұлғаю жиілігі екенін тексереміз. Егер ол өсіп жатқан массив болса, онда берілген массив монотонды массив болса, онда біз массивті тағы да айналып өтіп, оның [i]> = arr [i + 1] болуын тексеріп, азаятын массив екенін тексереміз. Егер бұл кішірейетін массив болса, онда берілген массив монотонды массив болады, әйтпесе ол монотонды массив емес.

Сондай-ақ, массивтің өсуін немесе азаюын тек қана бір өтпелі жол арқылы тексере аламыз. Біз isincr және isdec екі жалаушасын қолданамыз және оны шын мәнінде баптаймыз. Егер A [i]> A [i + 1] болса, онда isincr жалған болады, ал егер A [i] <A [i + 1] болса, онда isdec жалған болады. егер массив монотонды болса, онда isincr мен isdec-тің кем дегенде біреуі дұрыс болады. Егер екеуі де жалған болса, массив монотонды болмайды, өйткені екі жалған мән де массивтің мәні өсіп, кеміп жатқанын білдіреді.

 

код

C ++ монотонды массив LeetCode шешімі

#include <bits/stdc++.h> 
using namespace std; 
        bool isMonotonic(vector<int>& A) {
        bool isincr = true;
        bool isdec = true;
        int n=A.size();
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
    }

int main() 
{ 
 vector<int> arr = {1,2,4,5}; 
 cout <<boolalpha;
 cout<<isMonotonic(arr)<<endl; 
 return 0;
}
true

Java Monotonic Array LeetCode шешімі

import java.util.Arrays; 
public class Tutorialcup {
    public  static  boolean isMonotonic(int[] A) {
        boolean isincr = true;
        boolean isdec = true;
        int n=A.length;
        for (int i = 0; i < n- 1; ++i) {
            if (A[i] > A[i+1])
                isincr = false;
            if (A[i] < A[i+1])
               isdec = false;
        }

        return isincr || isdec;   
}
  public static void main(String[] args) {
    int [] arr = {1,2,4,5}; 
    boolean ans= isMonotonic(arr);
    System.out.println(ans);
  }
}
true

Монотонды массивтің күрделілігін талдау

Уақыт күрделілігі

Жоғарыда келтірілген кодтың уақыт күрделілігі O (N) өйткені біз массивтің монотонды массив екенін немесе болмауын тексеру үшін оны тек бір рет айналып өтеміз. Мұнда n - енгізу массивінің өлшемі.

Ғарыштың күрделілігі

Жоғарыда аталған кодтың кеңістігінің күрделілігі мынада O (1) өйткені біз жауаптарды сақтау үшін айнымалыны ғана қолданамыз.

Әдебиеттер тізімі