896. Monotonic Array（单调数列）

896. 单调数列

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true，否则返回 false。

 

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

 

提示：

1. 1 <= A.length <= 50000
2. -100000 <= A[i] <= 100000

解法一

//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int n = A.size();
        int signs = A[0] - A[n - 1];//+、-、0
        for(int i = 1; i < n; i++) {
            int diff = A[i - 1] - A[i];//求差
            
            //是否同号，否则返回false，<=号不可写成<
            if(diff != 0 && 1.0 * signs * diff <= 0) return false;
        }
        return true;
    }
};

思路：

先求出数组首元素和尾元素之差signs，将其正负符号作为假定的数组的增减性。如果这个数组是增序或减序，则每相邻两个元素之差的符号会与signs相同。不同则说明假设是错的，返回false。

代码说明：

1. 如果相邻两元素之差为0(diff == 0)，说明这两个元素不影响数组的增减性，可以直接跳过；
2. 如果diff不为0，说明此处有局部增/减，要判断其符号是否与signs相同。按其乘积正负号分，有三种情况：若乘积大于0说明同号（继续向后判断）；小于0则异号（应返回false）；等于0（因为前面已经排除了diff为0的情况，积为0说明signs为0，推翻了假设，所以应返回false） ；
3. 全部遍历完成说明满足要求，返回true。

2019/07/31 22:31