LeetCode #665. Non-decreasing Array

xiaoxiao2021-03-01  32

#665. Non-decreasing Array ##题目描述 Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

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

Example 2:

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

##思路 主要思路是,用ans来表示修改的次数,初始为0。 i从0到n-2,如果发现有array[i] > array[i + 1] (1 <= i < n),则分以下情况处理: (1)如果ans大于0,说明已经改了一个数,此时返回false; (2)如果ans等于0,则ans++,然后分以下情况处理: 1)i==0,此时只需将array[0]改为array[1]的值即可(往小的改); 2)i>0,此时比较array[i+1]和array[i-1]: 如果array[i+1] > array[i-1],则将array[i]改为array[i-1]或array[i+1]; 如果array[i+1] < array[i-1],则将array[i+1]改为array[i]。 只要出现了两次或以上的array[i] > array[i + 1] (1 <= i < n),就肯定不行,但只是这样还不行,还要判断特殊情况,例如数组[2,3,3,2,4],

##代码

class Solution { public: bool checkPossibility(vector<int>& nums) { int ans = 0; int i, j, k; if(nums.size() < 3) { return true; } for(i=0; i<nums.size()-1; i++) { if(nums[i] > nums[i+1]) { if(ans>0) { return false; } ans ++; if(i>0 && nums[i+1] < nums[i-1]){ nums[i+1] = nums[i]; } } } return true; } };
转载请注明原文地址: https://www.6miu.com/read-3349957.html

最新回复(0)