Решение за монотона низа LeetCode


Ниво на тешкотија Лесно
Често прашувано во Амазон Facebook
Низа

Проблем изјава

Во проблемот „Монотона низа“ ни е дадена низа. Нашата задача е да провериме дали низата е a монотоно низа или не.

Монотона низа е низа каде што елементите се сортираат во редослед на зголемување или во редослед на опаѓање. Ако низата е подредена според растечкиот редослед, тогаш за низата arr [], arr [i] <= arr [i + 1]. За низа подредени во опаѓачки редослед, arr [i]> = arr [i + 1].

Функцијата треба да се врати вистинита само кога низата е монотона. Во спротивно, вратете лажно.

пример

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

објаснување:  Во дадената низа за секој i arr [i]

Пристап

За да се реши овој проблем, многу е важно јасно да се разбере што е монотона низа.

монотона низа е низа во која ако нацртаме график помеѓу бројот на индексот и вредноста на тој индекс на низата, тогаш тој формира или монотоно зголемување или намалување на графот. Сликата подолу покажува монотоно зголемување и намалување на графиконот.

решение за лек код за монотона низа

Пристапот кон овој проблем е како, ние ќе ја пресечеме низата и ќе провериме дали е низа што се зголемува со проверка на arr [i] <= arr [i + 1]. Ако станува збор за низа што се зголемува, дадената низа е монотона низа на друго место, ние повторно ќе ја поминеме низата и ќе провериме дали е низа што се намалува со проверка дали arr [i]> = arr [i + 1]. Ако станува збор за низа што се намалува, дадената низа е монотона низа, не е монотона низа.

Исто така, можеме да провериме дали низата се зголемува или се намалува, користејќи само еден пресек. Useе користиме две знамиња isincr и isdec и ќе ги иницијализираме со true. Ако A [i]> A [i + 1] тогаш isincr ќе стане лажен и ако A [i] <A [i + 1] тогаш isdec ќе стане лажен. ако низата е монотона, тогаш барем едно од isincr и isdec ќе биде точно. Кога и двата се лажни, низата не е монотона бидејќи и лажните вредности сугерираат дека вредноста во низата се зголемува и се намалува.

 

Код

Решение LeetCode за монотона низа C ++

#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, решение 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

Анализа на комплексноста на монотоната низа

Временска сложеност

Временската сложеност на горенаведениот код е Тој) затоа што ја разгледуваме низата само еднаш за да провериме дали е монотона низа или не. Тука n е големината на влезната низа.

Комплексноста на просторот

Комплексноста на просторот на горенаведениот код е О (1) затоа што користиме само променлива за складирање одговори.

Референци