Leetcode (665) -- non decreasing column

Leetcode（665）—— Non decreasing Columns

subject

Give you a length of n Array of integers for nums , Please judge in most change 1 In the case of elements , Whether the subtracted array can become a non recursive column .

This is how we define a non decreasing column ： For any i (0 <= i <= n-2), Always satisfied nums[i] <= nums[i + 1].

Example 1：

Input : nums = [4,2,3]
Output : true
explain : You can do this by putting the first one 4 become 1 To make it a non decreasing column .

Example 2：

Input : nums = [4,2,1]
Output : false
explain : You can't change one element to a non decreasing column .

Tips ：

• n == nums.length
• 1 <= n <= 104
• -105 <= nums[i] <= 105

Answer key

Method 1 ： Greedy Algorithm

Ideas

​​   First, consider the following questions ： To make an array $\text{nums}$ Become a non decreasing column , How many... Are there at most in the array $i$ Satisfy $\text{nums}[i]>\text{nums}[i+1]$？

At most one .

​​   Suppose there are two different subscripts $i$, $j$ Satisfy the above inequality , Might as well set $i<j$.

1. if $i+1<j$, No matter how it is modified $\text{nums}[i]$ or $\text{nums}[i+1]$, Will not affect $\text{nums}[j]$ And $\text{nums}[j+1]$ Size relationship between ; modify $\text{nums}[j]$ or $\text{nums}[j+1]$ Also in the same way . therefore , In this case , We can't put $\text{nums}$ Become a non decreasing column .
2. if $i+1=j$, Then there are $\text{nums}[i]>\text{nums}[i+1]>\text{nums}[i+2]$. similarly , No matter how you modify one of the numbers , Can not make these three numbers into $\text{nums}[i]\le \text{nums}[i+1]\le \text{nums}[i+2]$ The size of the relationship .

​​   Is it enough to meet this condition ？ Does not , For arrays that meet this condition $[3,4,1,2]$ for , No matter how you modify it, you can't turn it into a non decreasing column .
​​   therefore , If you find a satisfaction $\text{nums}[i]>\text{nums}[i+1]$ Of $i$, In the revision $\text{nums}[i]$ or $\text{nums}[i+1]$ after , We need to check $\text{nums}$ Whether it becomes a non decreasing column .

​​   We can $\text{nums}[i]$ Change to less than or equal to $\text{nums}[i+1]$ Number of numbers , However, due to the need to ensure $\text{nums}[i]$ Not less than the number before it ,$\text{nums}[i]$ The bigger the better , So will $\text{nums}[i]$ Modified into $\text{nums}[i+1]$ It's the best ; Empathy , about $\text{nums}[i+1]$, Modified into $\text{nums}[i]$ It's the best .

Can I traverse only once $\text{nums}$ Array? ？
​​   modify $\text{nums}[i]$ by $\text{nums}[i+1]$ after , And you need to make sure $\text{nums}[i-1]\le \text{nums}[i]$ Still established , namely $\text{nums}[i-1]\le \text{nums}[i+1]$, If this inequality does not hold, the entire array must not be non decreasing , It needs to be modified $\text{nums}[i+1]$ by $\text{nums}[i]$. After modification , Then judge the size relationship of subsequent numbers . Statistics in traversal $\text{nums}[i]>\text{nums}[i+1]$ The number of times , If it is more than once, it can be returned directly $\text{false}$.

Code implementation

class Solution {
    
public:
    bool checkPossibility(vector<int>& nums) {
    
        // 1. Find the first pair of values that cause the sequence to be non decreasing （ The former is greater than the latter ）, Return if not found true
        // 2. Find the first pair of values that cause the sequence to be non decreasing , Judge whether the former of the first value is less than or equal to the second value , if true Continued to , if false be 
        //  Determine whether the first value is less than or equal to the latter of the second value , if true Continued to , Otherwise return to false
        // 3. Then judge whether the sequences are all non decreasing columns , That is, whether we can find the second pair of values that cause the sequence to be non decreasing , Found return false, Otherwise return to true
        int size = nums.size(), non_value = 0;  // non_value  Indicates the number of places that cause the sequence to be non decreasing 
        if(size <= 2) return true;  //  If it is less than or equal to 2, It must be able to change at most 1 In the case of elements, the array becomes a non - decreasing column 
        for(int n = 1; n < size; n++){
    
            if(nums[n-1] > nums[n]){
    
                //  Two non decreasing values 
                if(++non_value <= 1) {
    
                    //  Also note whether it is  n-1  Whether it is the first value and  n  Whether it is a special case of the last value 
                    if(n == 1 || nums[n-2] <= nums[n] || n == size-1 || nums[n-1] <= nums[n+1]) continue;
                    else return false;
                }else return false;
            }
        }
        return true;
    }
};

Complexity analysis

Time complexity ：$O(n)$, among $n$ It's an array $\text{nums}$ The length of .
Spatial complexity ：$O(1)$