[数据结构与算法]LeetCode-665. Non-decreasing Array [C++][Java]

LeetCode-665. Non-decreasing ArrayLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/non-decreasing-array/

题目描述

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
• -105?<= nums[i] <= 105

解题思路

【C++】

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int cnt = 0, len = nums.size();
        for (int i=1; i<len; ++i) {
            if (nums[i] < nums[i-1]) {
                cnt++;
                if (i >= 2 && nums[i] < nums[i-2]) {nums[i] = nums[i-1];}
                else {nums[i-1] = nums[i];}
            }
        }
        return cnt <= 1;
    }
};

【Java】

class Solution {
    public boolean checkPossibility(int[] nums) {
        int cnt = 0;
        for (int i=1; i<nums.length; ++i) {
            if (nums[i] < nums[i-1]) {
                cnt++;
                if (i>=2 && nums[i] < nums[i-2]) {nums[i] = nums[i-1];}
                else {nums[i-1] = nums[i];}
            }
        }
        return cnt <= 1;
    }
}