单调数组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解决方案Pin

解决此问题的方法就像,我们将遍历数组并通过检查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) 因为我们只使用一个变量来存储答案。

參考資料