Monotonic Array LeetCode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Facebook
Array

პრობლემის განცხადება

პრობლემში "ერთფეროვანი მასივი" ჩვენ გვეძლევა მასივი. ჩვენი ამოცანაა შეამოწმოთ არის თუ არა მასივი a ერთფეროვანი მასივი თუ არა.

მონოტონური მასივი არის მასივი, სადაც ელემენტები ან დალაგებულია მზარდი თანმიმდევრობით ან კლებადობით. თუ მასივი დალაგებულია მზარდი თანმიმდევრობით, მასივის arr [] - ისთვის, arr [i] <= arr [i + 1]. მასივისთვის, რომელიც დალაგებულია კლებადი თანმიმდევრობით, arr [i]> = arr [i + 1].

ფუნქცია უნდა დაბრუნდეს ჭეშმარიტი მხოლოდ მაშინ, როდესაც მასივი ერთფეროვანია. წინააღმდეგ შემთხვევაში, ყალბი დაბრუნება.

მაგალითი

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

განმარტება:  მოცემულ მასივში თითოეული i ar [i]

მიდგომა

ამ პრობლემის მოსაგვარებლად ძალზე მნიშვნელოვანია იმის გარკვევა, თუ რა არის ერთფეროვანი მასივი.

მონოტონური მასივი არის მასივი, რომელშიც თუ გრაფიკზე ვდგამთ ინდექსის რიცხვს და მნიშვნელობას მასივის ამ ინდექსში, მაშინ იგი ქმნის ან ერთფეროვან მზარდ ან შემცირებულ გრაფიკს. ქვემოთ მოცემულ სურათზე მოცემულია ერთფეროვანი მზარდი და შემცირებული გრაფიკი.

leetcode გადაწყვეტა Monotonic Array

ამ პრობლემისადმი მიდგომა ჰგავს, ჩვენ გადავხედავთ მასივს და შევამოწმებთ არის თუ არა ის მზარდი მასივი, arr [i] <= arr [i + 1]. თუ ეს არის მზარდი მასივი, მაშინ მოცემული მასივი არის ერთფეროვანი მასივი, სხვა შემთხვევაში ჩვენ კვლავ გადავკვეთთ მასივს და შეამოწმებთ არის თუ არა შემცირებადი მასივი, თუ გადავამოწმებთ arr [i]> = arr [i + 1]. თუ ეს არის კლებადი მასივი, მაშინ მოცემული მასივი არის ერთფეროვანი მასივი, სხვა შემთხვევაში ეს არ არის ერთფეროვანი მასივი.

ასევე შეგვიძლია შეამოწმოთ, არის თუ არა მასივი იზრდება თუ მცირდება მხოლოდ ერთი გადაკვეთის გამოყენებით. ჩვენ გამოვიყენებთ ორი დროშის isincr და isdec და დავიწყებთ მას true- ს. თუ 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

ჯავის ერთფეროვანი მასივის 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) რადგან პასუხების შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა