Skip to content

Latest commit

 

History

History
78 lines (61 loc) · 1.79 KB

File metadata and controls

78 lines (61 loc) · 1.79 KB

665. Non-decreasing Array

Leetcode link

解题思路

题目给定一个数组 nums,要求我们判断在对多改变一个元素的情况下是否能将该数组变为升序(包含相等)


本题的关卡有两个:

  • 在满足题目的要求下最多能有几个非升序的元素呢?
    • 一个
  • 在发现有非升序的元素 nums[i] 时,应该如何改变元素呢?
    • 第一种情况 nums[i + 1] < nums[i - 1] :这种情况需要将 nums[i + 1] 变为 nums[i]
    • 第二种情况 nums[i + 1] >= nums[i - 1]:这种情况需要将 nums[i] 变为 nums[i + 1]

C++

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        bool flag = false;
        for(int i = 0;i < nums.size() - 1;i++) {
            int x = nums[i];
            int y = nums[i + 1];
            if(x > y) {
                if(flag) {
                    return false;
                }
                flag = true;
                if(i >0 && y < nums[i - 1]) {
                    nums[i + 1] = x;
                }
            }
        }
        return true;
    }
};

Javascript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
    let flag = false;
    for(let i = 0;i < nums.length - 1;i++) {
        let x = nums[i];
        let y = nums[i + 1];
        if(x > y) {
          // 只允许更改一次
            if(flag) {
                return false;
            }
            flag = true;
          // 第一种情况
            if(i>0 && y < nums[i - 1]) {
                nums[i + 1] = x;
            }
          // 第二种情况其实无需更改,因为后面的遍历不会访问到了
        }
    }
    return true;
};