LeetCode-判断单调数组

今天看了道算法题，

判断一个数组是否为单调数组，是返回 true，不是返回 false。

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

思考

单调即数组后一项都比前一项大，或都比前一项小
重点是 每一项 和 比较

• 要能遍历每一项，需要循环数组
• 比较，这个就有文章了

怎么比较

因为有两种情况

• 要么后一项都比前一项大
• 要么后一项都比前一项小

因此最简单的是两个if判断一下，于是就有

/**
 * @param {number[]} list
 * @return {boolean}
 */
const isMonotonic = function(list) {
    return incMon(list) || decMon(list)
};

const incMon = function(list) {
    let isMon = false;
    for(let i = 0; i<list.length-1; i+=1){
        if(list[i]-list[i+1] > 0) isMon = true
    }
    return isMon;
};

const decMon = function(list) {
    let isMon = false;
    for(let i = 0; i<list.length-1; i+=1){
        if(list[i]-list[i+1] < 0) isMon = true
    }
    return isMon;
};

emmm，上面这段是有bug的，因为就算循环了，但判断条件只要有一项满足即为true，因此无法检测类似[1,3,2]这种数组，怎么办？

问题在哪呢？

上面两个incMon和decMon的前提假设是传入的数组不是单调数组，如果假设传入是单调，只要判断出有一项不符合，就返回false，那应该就不会有问题了。

于是，改为：

/**
 * @param {number[]} list
 * @return {boolean}
 */
const isMonotonic = function(list) {
    return incMon(list) || decMon(list)
};

const incMon = function(list) {
    let isMon = true;
    for(let i = 0; i<list.length-1; i+=1){
        if(list[i]-list[i+1] < 0) isMon = false;
    }
    return isMon;
};

const decMon = function(list) {
    let isMon = true;
    for(let i = 0; i<list.length-1; i+=1){
        if(list[i]-list[i+1] > 0) isMon = false;
    }
    return isMon;
};

嗯，

条件判断应该尽量判断特殊情况。

再看看刚才代码，感觉两个增减判断函数里for循环功能类似，仅判断条件不一样，第六感告诉我这还有优化空间。

心中默念：

写代码的目的是为了有一天能不写代码。

来，继续。

优化

非单调的情况是

• 递增的出现list[i]-list[i+1] > 0
• 递减的出现list[i]-list[i+1] < 0

然后可以有

/**
 * @param {number[]} list
 * @return {boolean}
 */
const isMonotonic = function(list) {
    let incFlag = true;
    let decFlag = true;
    for(let i = 0, i<list.length-1,i+=1){
        if(list[i]-list[i+1]>0) incFlag = false;
        if(list[i]-list[i+1]<0) decFlag = false;
    }
    return incFlag || decFlag
}

嗯，看着优雅多了

ShowCase

Input: [4]
Output: true

咦，当数组只有一个数的时候必定是单调函数，就不用再费事去循环了！
再优化下，加个判断。

/**
 * @param {number[]} list
 * @return {boolean}
 */
const isMonotonic = function(list) {
+    if(list.length <= 1) return true;
    let incFlag = true;
    let decFlag = true;
    for(let i = 0, i<list.length-1,i+=1){
        if(list[i]-list[i+1]>0) incFlag = false;
        if(list[i]-list[i+1]<0) decFlag = false;
    }
    return incFlag || decFlag
}

嗯，这回应该不错了。

还有别的方法嘛？

有的。

const isMonotonic = function(A) {
  let flag = 0; //increasing - 1; decreasing -2
  if (A.length <= 1) return true;

  for (let i = 1; i < A.length; i++) {
    if (A[i] > A[i - 1]) {
      if (flag === 2) return false;
      flag = 1;
    } else if (A[i] < A[i - 1]) {
      if (flag === 1) return false;
      flag = 2;
    }
  }

  return true;
};

本文完。