മോണോടോണിക് അറേ ലീറ്റ്കോഡ് പരിഹാരം  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫേസ്ബുക്ക്
അൽഗോരിതം അറേ കോഡിംഗ് അഭിമുഖം അഭിമുഖം ലീട്ട് കോഡ് LeetCodeSolutions

പ്രശ്നം പ്രസ്താവന  

“മോണോടോണിക് അറേ” എന്ന പ്രശ്‌നത്തിൽ ഞങ്ങൾക്ക് ഒരു അറേ നൽകിയിരിക്കുന്നു. അറേ a ആണോയെന്ന് പരിശോധിക്കുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല മോണോടോണിക് അറേ അല്ലെങ്കിൽ ഇല്ല.

ഘടകങ്ങൾ ക്രമത്തിലോ കുറയുന്ന ക്രമത്തിലോ അടുക്കിയിരിക്കുന്ന ഒരു അറേയാണ് മോണോടോണിക് അറേ. അറേ വർദ്ധിക്കുന്ന ക്രമത്തിൽ അടുക്കിയിട്ടുണ്ടെങ്കിൽ, ഒരു അറേ അറയ്‌ക്കായി [], arr [i] <= arr [i + 1]. ക്രമം കുറയ്ക്കുന്നതിന് അടുക്കിയ ഒരു അറേയ്‌ക്ക്, arr [i]> = arr [i + 1].

അറേ മോണോടോണിക് ആയിരിക്കുമ്പോൾ മാത്രമേ പ്രവർത്തനം ശരിയാകൂ. അല്ലെങ്കിൽ, തെറ്റായി മടങ്ങുക.

ഉദാഹരണം  

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

വിശദീകരണം:  ഓരോന്നിനും നൽകിയിരിക്കുന്ന അറേയിൽ ഞാൻ [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 എന്നിവയിലെങ്കിലും ശരിയാകും. രണ്ടും തെറ്റായതാണെങ്കിൽ അറേ ഏകതാനമല്ല, കാരണം രണ്ട് തെറ്റായ മൂല്യങ്ങളും സൂചിപ്പിക്കുന്നത് അറേയിലെ മൂല്യം വർദ്ധിക്കുകയും കുറയുകയും ചെയ്യുന്നു എന്നാണ്.

 

കോഡ്  

സി ++ മോണോടോണിക് അറേ ലീറ്റ്കോഡ് പരിഹാരം

#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

ജാവ മോണോടോണിക് അറേ ലീറ്റ്കോഡ് പരിഹാരം

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) കാരണം ഉത്തരങ്ങൾ‌ സംഭരിക്കുന്നതിന് ഞങ്ങൾ‌ ഒരു വേരിയബിൾ‌ മാത്രം ഉപയോഗിക്കുന്നു.

അവലംബം