665. Non-decreasing Array

by

665. Non-decreasing Array

Medium

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • -10^5 <= nums[i] <= 10^5

思路

遍历的时候以 4 个数字为一段 prev_num, nums[i], nums[i + 1], nums[i + 2]。

当首次检测到 nums[i] > nums[i + 1] 时，说明此处需要修改。可能存在两种修改方式：

  1. 修改 nums[i] 使得 prev_num <= nums[i] <= nums[i + 1]，需满足 prev_num <= nums[i + 1]；
  2. 修改 nums[i + 1] 使得 nums[i] <= nums[i + 1] <= nums[i + 2]，需满足 nums[i] <= nums[i + 2]。

两种方式的共同前提是 prev_num <= nums[i + 2]，若此前提不满足则必无法只改一个数达成要求。

（注：若 i + 2 超出范围，说明 nums[i + 1] 是最后一个数，此时只需修改 nums[i + 1] 即可达成要求。）

首次修改完成后，将 modified_flag 置 true，下一次再检测到异常序列则返回 false。

循环结束前更新 prev_num。

遍历完成后返回 true。

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int prev_num = INT_MIN;
        int steps = nums.size() - 1;
        bool modified_flag = false;
        for (int i = 0; i < steps; ++i) {
            if (nums[i] > nums[i + 1]) {
                if (modified_flag) return false;
                if (i + 2 <= steps) {
                    if (prev_num <= nums[i + 2] &&
                        (prev_num <= nums[i + 1] || nums[i] <= nums[i + 2])) {}
                    else return false;
                }
                modified_flag = true;
            }
            prev_num = nums[i];
        }
        return true;
    }
};

Runtime: 12 ms, faster than 99.58% of C++ online submissions for Non-decreasing Array.

Memory Usage: 26.8 MB, less than 93.24% of C++ online submissions for Non-decreasing Array.

Leave a Comment