leetcode896

leetcode896

题目意思

题目的意思是给定一个数组,如何判断其是否单调。或增或减。

解决方法

我想的是先找出第一个两个数不相等的位置,然后看看他们是什么关系,然后根据这个关系再继续往后面去看。

python的代码如下

class Solution(object):
    def isMonotonic(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        if len(A)<=2:
            return True
        
        idx = -1
        for i in range(len(A)-1):
            if A[i]!=A[i+1]:
                idx = i
                break
        if idx == -1:    # 说明是同一个常数
            return True
        
        increasing = A[idx]<A[idx+1]   # 看他们的关系
        
        # 然后看后面的是否满足这种关系。
        if increasing: 
            for i in range(idx+1, len(A)-1):
                if A[i]<=A[i+1]:
                    continue
                else:
                    return False
            return True
        else:
            for i in range(idx+1, len(A)-1):
                if A[i]>=A[i+1]:
                    continue
                else:
                    return False
            return True
        

时间复杂度是O(n).

当然如果用库的话,更方便一些,可能时间复杂度高一些,比如用sorted,一行就写完了

return sorted(A)==A or sorted(A, reverse=True)==A

但是这里面涉及到的有排序,大致是O(nlogn)的复杂度。

或者下面的这样也行

return sorted(A)==A or sorted(A)==A[::-1]

还有一种方法是先直接判断第一个元素和最后一个元素的关系,如果它们相等,再看中间有没有不等的,如果第一个比较小的,就判断是不是递增,否则就判断是不是递减。 上面的代码还可以修改成,把一个函数传进去作为参数,但是可能调用函数成本有些高了,因为要调用好多次。

用c++写刚才的想法的话是

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int len = A.size();
        if(len<=2){
            return true;
        }
        
        if(A[0]==A[len-1]){
            for(int i=1;i<len-1;i++){
                if(A[i]!=A[0]){
                    return false;
                }
            }
            return true;
        }else if(A[0]<A[len-1]){
            for(int i=0;i<len-1;i++){
                if(A[i]>A[i+1]){
                    return false;
                }
            }
            return true;
        }else{
            for(int i=0;i<len-1;i++){
                if(A[i]<A[i+1]){
                    return false;
                }
            }
            return true;
        }
        
        
    }
};

写的有点丑感觉。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦