c++ greedy solution easy to understand


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

    The key is we have to make sure num[0...i] is non-descending and num[i+1] is as low as possible.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.