Interesting


  • 0
    A

    Interesting problem.

    The problem basically ask whether it possible to modify a value to make a given array non-strictly increasing(including equality).

    Brute force search for the problem is to check every combination (p,v) of the modifying position p and the value v after modification. Because v have a large range. Search method is not applicable.

    Notice there are strong constraints on the replaced value, which is to make nums[0]<=...<=nums[i-1]<=nums[i]<=nums[i+1]<=....<=nums[n-1] holds.

    We can have a dynamic programming algorithm to solve the problem. Because if nums[0:n] is non-decreasing, nums[0:i] must also be non-decreasing. So the sub-problem become the minimum modifying to make nums[0:i] non-decreasing.

    If nums[i]<nums[i+1], no modifying work is needed to expand solution from i to i+1.

    If nums[i]>nums[i+1], we got two options to expand our solution.One is to lower the nums[i], the other is to raise the nums[i+1]. The range to decrease nums[i] depends on whether nums[i-1]<=nums[i] still holds.

    Here comes the greedy solution. Since the modified value is under strong constraint, we should do minimum modifying to best preserve the order relation. so let nums[i] = num[i+1] when to do the minimum decreasing, when that don't break the original nums[0:i] solution. Or just increasing nums[i+1] to expand solution to nums[0:i+1].

    /The greedy proofs to be done./

    class Solution(object):
        def checkPossibility(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            mi = min(nums)
            nums = [mi]+nums
            cnt = 0
            for i in range(1,len(nums)-1):
                if nums[i]>nums[i+1]:
                    if nums[i-1]<=nums[i+1]:
                        nums[i]=nums[i+1]
                        cnt += 1
                    else:
                        nums[i+1]=nums[i]
                        cnt += 1
            return cnt<=1
    

Log in to reply
 

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