leetcode655

leetcode655

这个题目是单调递增的数组判断,即给定一个数组,如果允许最多修改其中的一个元素的话,问它能不能成为一个单调递增的数组。 比如[4,2,3]就可以,[4,2,1]就不行。 因为[4,2,3]可以把4变成1,而[4,2,1]即使把4变成1了也不行。

我的想法比较笨,暂时还没想到更好的办法,就是先遍历,遇到这个数比其右边的数要大的话,就修改这个数,但是具体如何修改,要看情况,

比如,如果是[1,4,2,3]的话,就可以把4换成1就可以了(因为1比2要小,即左边的没有右边的大),但是如果是[3,3,4,2,4]的话,当前的数是4,而这时候需要把其右边的数2换成当成的4,因为左边的3比右边的2要大。

因为只需最多换一个数,所以如果超过1了就错,全部通过的话就是True.

python

class Solution(object):
    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums)<=2:
            return True
        
        num = 0
        for i in range(len(nums)-1):
            if nums[i]>nums[i+1]:
                num += 1
                # 1423  # two cases,modify nums[i] smaller, modify nums[i+1] larger
                if i ==0:
                    nums[0] =nums[1]
                elif nums[i-1]<=nums[i+1]:  #1423   4--->1
                    nums[i] = nums[i-1]    
                else:               # 33424     2---->4
                    nums[i+1] = nums[i]          
            if num>1:
                return False
        return True
               

c++

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

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦