單調數組LeetCode解決方案


難度級別 容易獎學金
經常問 亞馬遜 Facebook
排列

問題陳述

在問題“單調數組”中,我們得到了一個數組。 我們的任務是檢查數組是否為 單調的 數組與否。

單調數組是一種元素按升序或降序排序的數組。 如果數組按升序排序,則對於數組arr [],arr [i] <= arr [i + 1]。 對於以降序排序的數組,arr [i]> = arr [i + 1]。

僅當數組為單調時,該函數才應返回true。 否則,返回false。

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

說明:  在給定的數組中,每個i arr [i]

途徑

為了解決這個問題,重要的是要清楚地了解什麼是單調數組。

單調數組是一個數組,其中,如果我們在該索引的索引號和值之間繪製一個圖,則該圖將形成單調遞增或遞減的圖。 下圖顯示了單調遞增和遞減的圖形。

單調數組的leetcode解決方案

解決此問題的方法就像,我們將遍歷數組並通過檢查arr [i] <= arr [i + 1]來檢查它是否為遞增數組。 如果是遞增數組,則給定數組是單調數組,否則我們將再次遍歷該數組,並通過檢查arr [i]> = arr [i + 1]來檢查它是否是遞減數組。 如果是遞減數組,則給定數組是單調數組,否則不是單調數組。

我們還可以僅通過一次遍歷檢查數組是在增加還是在減少。 我們將使用兩個標誌isincr和isdec並將其初始化為true。 如果A [i]> A [i + 1],則isincr將為false;如果A [i] <A [i + 1],則isdec將為false。 如果數組是單調的,則isincr和isdec中的至少一個為true。 如果兩個均為假,則表示數組不是單調的,因為兩個假值都表明該數組中的值在增加和減少。

 

推薦碼

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單調數組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) 因為我們只使用一個變量來存儲答案。

參考