115 - 665 非递减数列

题目

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

示例 1:

输入: [4,2,3] 输出: True 解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

输入: [4,2,1] 输出: False 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明: n 的范围为 [1, 10,000]。

解答

感觉就是单纯搞脑子的题。。。

https://leetcode-cn.com/problems/non-decreasing-array/solution/javafei-di-jian-shu-lie-by-but-2/

1. 三个以内，怎样排都行

2. 三个以上，假设有三个数x/y/z。如果x>z，就让z=y；如果x<z，就让y=z

3. 如果三个以上变更超过两次，就不行

var checkPossibility = function(N) {
  if (N.length < 3) {
    return true;
  }
  let count = 0;
  for (let i = 0; i < N.length - 1; i++) {
    if (N[i + 1] < N[i]) {
      count++;
      if (count > 1) {
        return false
      }
      if (i > 0 && N[i - 1] > N[i + 1]) {
        N[i + 1] = N[i]
      }
    }
  }
  return true
};

Runtime: 76 ms, faster than 20.89% of JavaScript online submissions for Non-decreasing Array.

Memory Usage: 36.8 MB, less than 100.00% of JavaScript online submissions for Non-decreasing Array.

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return True
        count = 0
        for i in range(0, len(nums)-1):
            if nums[i+1] < nums[i]:
                count += 1
                if count > 1:
                    return False
                if i > 0 and nums[i-1] > nums[i+1]:
                    nums[i+1] = nums[i]
        return True

Runtime: 224 ms, faster than 51.37% of Python3 online submissions for Non-decreasing Array.

Memory Usage: 15.1 MB, less than 6.67% of Python3 online submissions for Non-decreasing Array.

func checkPossibility(nums []int) bool {
    if len(nums) < 3 {
        return true
    }
    count := 0
    for i := 0; i < len(nums)-1; i++ {
        if nums[i+1] < nums[i] {
            count++
            if count > 1 {
                return false
            }
            if i > 0 && nums[i-1] > nums[i+1] {
                nums[i+1] = nums[i]
            }
        }
    }
    return true
}

Runtime: 24 ms, faster than 85.19% of Go online submissions for Non-decreasing Array.

Memory Usage: 6.2 MB, less than 100.00% of Go online submissions for Non-decreasing Array.

https://leetcode.com/problems/non-decreasing-array/discuss/106816/Python-Extremely-Easy-to-Understand

这种做法的思路一样，但实现起来更加快

var checkPossibility = function(N) {
  let count = 0;
  for (let i = 1; i < N.length; i++) {
    if (N[i - 1] > N[i]) {
      count++;
      if (i < 2 || N[i - 2] <= N[i]) {
        N[i - 1] = N[i]
      } else {
        N[i] = N[i - 1]
      }
    }
  }
  return count <= 1
};

Runtime: 64 ms, faster than 79.50% of JavaScript online submissions for Non-decreasing Array.

Memory Usage: 36.6 MB, less than 100.00% of JavaScript online submissions for Non-decreasing Array.

可能是因为，上一种做法每次for循环都要判断导致降低了速度

毕竟中招是小概率事件，每次判断有点不值得。最好是最后一起判断

func checkPossibility(nums []int) bool {
    cnt := 0
    for i := 1; i < len(nums) && cnt <= 1; i++ {
        if nums[i-1] > nums[i] {
            cnt++
            if i-2 < 0 || nums[i-2] <= nums[i] {
                nums[i-1] = nums[i]
            } else {
                nums[i] = nums[i-1]
            }
        }
    }
    return cnt <= 1
}

Runtime: 24 ms, faster than 85.07% of Go online submissions for Non-decreasing Array.

Memory Usage: 6.2 MB, less than 100.00% of Go online submissions for Non-decreasing Array.

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        count = 0
        for i in range(1, len(nums)):
            if nums[i-1] > nums[i]:
                count += 1
                if i < 2 or nums[i-2] <= nums[i]:
                    nums[i-1] = nums[i]
                else:
                    nums[i] = nums[i-1]
        return count <= 1

Runtime: 264 ms, faster than 8.52% of Python3 online submissions for Non-decreasing Array.

Memory Usage: 15.1 MB, less than 6.67% of Python3 online submissions for Non-decreasing Array.