Leetcode - 665. Non-decreasing Array

문제

주어진 배열에서 값을 1개만 바꿨을때, 인덱스값이 커지면서 요소의 값들이 점차 증가하거나 같은(== 감소하지 않는) 배열이 되는지 확인하기

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

해결 O(N^2)

brute force로 풀어봄. 배열값중 하나씩 조건을 만족하는 값으로 바꾼뒤, 배열을 순회하면서 값이 descreaing 하지 않았다면 true리턴. 그래도 의외로 pass는 되었음 (192 ms, faster than 5.10% of C++)

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

해결 O(N)

생각해보면 O(N)에 해결이 가능함. 우선 [i-1]이 [i]보다 큰지 체크. 그런부분이 두번 나오면 false.
그러면 아래의 경우는 오답이 됨.

4 5 1 2  -> 한번만 나오지만 false가 정답임.
  ^ ^
4 5 1
4 5 1 8
  ^

만약 [i-1]이 [i]보다 큰경우, [i-2]가 [i]보다 크다면 [i]를 [i-1]로 교체하고 계속 체크.
그 다음 루프에서 감소구간이 한번더 나온다면 false정답.

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

                if (i > 1 && nums[i - 2] > nums[i])
                    nums[i] = nums[i-1];
            }
        }
        return true;
    }
};