美文网首页程序员算法算法提高之LeetCode刷题
LeetCode.896-单调数组(Monotonic Arra

LeetCode.896-单调数组(Monotonic Arra

作者: 程序员小川 | 来源:发表于2019-06-06 08:46 被阅读16次

    这是悦乐书的第345次更新,第369篇原创

    01 看题和准备

    今天介绍的是LeetCode算法题中Easy级别的第210题(顺位题号是896)。如果数组单调递增或单调递减,则数组是单调的。如果对于所有i <= j,A[i] <= A[j],则数组A是单调递增的。如果对于所有i <= j,A[i] >= A[j],则数组A是单调递减的。当且仅当给定的数组A是单调的时,才返回true。例如:

    输入:[1,2,2,3]
    输出:true

    输入:[6,5,4,4]
    输出:true

    输入:[1,3,2]
    输出:false

    输入:[1,2,4,5]
    输出:true

    输入:[1,1,1]
    输出:true

    注意

    • 1 <= A.length <= 50000

    • -100000 <= A [i] <= 100000

    02 第一种解法

    使用两个循环,一个判断是否递增,一个判断是否递减,只要其中一个符合条件即可返回true。

    public boolean isMonotonic(int[] A) {
        return isIncrease(A) || isDecrease(A);
    }
    
    public boolean isIncrease(int[] A) {
        for (int i=0; i<A.length-1; i++) {
            if (A[i] > A[i+1]) {
                return false;
            }
        }
        return true;
    }
    
    public boolean isDecrease(int[] A) {
        for (int i=0; i<A.length-1; i++) {
            if (A[i] < A[i+1]) {
                return false;
            }
        }
        return true;
    }
    

    03 第二种解法

    也可以只是用一次循环。

    public boolean isMonotonic2(int[] A) {
        boolean isincrease = true;
        boolean isdecrease = true;
        int n = A.length;
        for (int i=0; i<n-1; i++) {
            isincrease = isincrease && A[i] <= A[i+1];
            isdecrease = isdecrease && A[i] >= A[i+1];
        }
        return isincrease || isdecrease;
    }
    

    04 第三种解法

    针对第二种解法,我们分两种情况分别处理了isincrease、isdecrease两个变量。

    public boolean isMonotonic3(int[] A) {
        boolean isincrease = true;
        boolean isdecrease = true;
        int n = A.length;
        for (int i=0; i<n-1; i++) {
            if (A[i] < A[i+1]) {
                isdecrease = false;
            }
            if (A[i] > A[i+1]) {
                isincrease = false;
            }
        }
        return isincrease || isdecrease;
    }
    

    05 第四种解法

    也可以借助包装类Integercompare方法,比较相邻两个元素的大小,另外使用一个变量存储上一次比较的结果,每次做完新的比较后,用新的结果和前一次的结果比较,只要前后两次比较结果不同,可以直接返回false。

    public boolean isMonotonic4(int[] A) {
        int flag = 0, n = A.length;
        for (int i=0; i<n-1; i++) {
            int num = Integer.compare(A[i], A[i+1]);
            if (num != 0) {
                if (flag != 0 && flag != num) {
                    return false;
                }
                flag = num;
            }
        }
        return true;
    }
    

    06 小结

    算法专题目前已连续日更超过六个月,算法题文章213+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

    以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

    相关文章

      网友评论

        本文标题:LeetCode.896-单调数组(Monotonic Arra

        本文链接:https://www.haomeiwen.com/subject/tofyxctx.html