[LeetCode] 896. Monotonic Array 单调数组

ゝ一纸荒年。 2021-12-10 05:45 190阅读 0赞

An array is *monotonic* if it is either monotone increasing or monotone decreasing.

An array `A` is monotone increasing if for all `i <= j`, `A[i] <= A[j]`.  An array `A` is monotone decreasing if for all `i <= j`, `A[i] >= A[j]`.

Return `true` if and only if the given array `A` is monotonic.

Example 1:

Input: [1,2,2,3]
    Output: true

Example 2:

Input: [6,5,4,4]
    Output: true

Example 3:

Input: [1,3,2]
    Output: false

Example 4:

Input: [1,2,4,5]
    Output: true

Example 5:

Input: [1,1,1]
    Output: true

Note:

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

这道题让我们判断一个数组是否单调，单调数组就是说这个数组的数字要么是递增的，要么是递减的，不存在一会儿递增一会儿递减的情况，即不会有山峰存在。这里不是严格的递增或递减，是允许有相同的数字的。那么我们直接将相邻的两个数字比较一下即可，使用两个标识符，inc 和 dec，初始化均为 true，我们开始时假设这个数组既是递增的又是递减的，当然这是不可能的，我们会在后面对其进行更新。在遍历数组的时候，只要发现某个数字大于其身后的数字了，那么 inc 就会赋值为 false，同理，只要某个数字小于其身后的数字了，dec 就会被赋值为 false，所以在既有递增又有递减的数组中，inc 和 dec 都会变为 false，而在单调数组中二者之间至少有一个还会保持为 true，参见代码如下：

解法一：

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

跟上面的解法思路很像，只不过没有用 bool 型的，而是用了整型数字来记录递增和递减的个数，若是单调数组，那么最终在 inc 和 dec 中一定会有一个值是等于数组长度的，参见代码如下：

解法二：

class Solution {
    public:
        bool isMonotonic(vector<int>& A) {
            int inc = 1, dec = 1, n = A.size();
            for (int i = 1; i < n; ++i) {
                inc += (A[i - 1] <= A[i]);
                dec += (A[i - 1] >= A[i]);
            }
            return (inc == n) || (dec == n);
        }
    };

Github 同步地址:

[https://github.com/grandyang/leetcode/issues/896][https_github.com_grandyang_leetcode_issues_896]

参考资料：

[https://leetcode.com/problems/monotonic-array/][https_leetcode.com_problems_monotonic-array]

[https://leetcode.com/problems/monotonic-array/discuss/165889/C%2B%2BJavaPython-One-Pass-O(N)][https_leetcode.com_problems_monotonic-array_discuss_165889_C_2B_2BJavaPython-One-Pass-O_N]

[https://leetcode.com/problems/monotonic-array/discuss/172578/Java-O(n)-simple-solution][https_leetcode.com_problems_monotonic-array_discuss_172578_Java-O_n_-simple-solution]

[LeetCode All in One 题目讲解汇总(持续更新中...)][LeetCode All in One _...]

转载于:https://www.cnblogs.com/grandyang/p/10961560.html

[https_github.com_grandyang_leetcode_issues_896]: https://github.com/grandyang/leetcode/issues/896
[https_leetcode.com_problems_monotonic-array]: https://leetcode.com/problems/monotonic-array/
[https_leetcode.com_problems_monotonic-array_discuss_165889_C_2B_2BJavaPython-One-Pass-O_N]: https://leetcode.com/problems/monotonic-array/discuss/165889/C%2B%2BJavaPython-One-Pass-O%28N%29
[https_leetcode.com_problems_monotonic-array_discuss_172578_Java-O_n_-simple-solution]: https://leetcode.com/problems/monotonic-array/discuss/172578/Java-O%28n%29-simple-solution
[LeetCode All in One _...]: https://www.cnblogs.com/grandyang/p/4606334.html