text: #!/usr/bin/env python3
  # -*- coding:utf-8 -*-
  # author: bigfoolliu
  
  
  """
  给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
  
  我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
  
   
  
  示例 1:
  
  输入: nums = [4,2,3]
  输出: true
  解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
  示例 2:
  
  输入: nums = [4,2,1]
  输出: false
  解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
   
  
  提示：
  
  1 <= n <= 10 ^ 4
  - 10 ^ 5 <= nums[i] <= 10 ^ 5
  
  
  来源：力扣（LeetCode）
  链接：https://leetcode-cn.com/problems/non-decreasing-array
  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
  """
  
  import doctest
  from typing import List
  
  
  class Solution:
      """
      >>> s = Solution()
      >>> s.checkPossibility([4, 2, 3])
      True
      >>> s.checkPossibility([4, 2, 1])
      False
      """
  
      def checkPossibility(self, nums: List[int]) -> bool:
          """
          贪心算法
  
          维持一个非递减的数列，所以遇到递减的情况时（nums[i] > nums[i + 1]），要么将前面的元素缩小，要么将后面的元素放大。
          [3, 4, 2, 3]
  
          4 > 2,可以选择将4缩小或者将2放大，但是：
              - 如果将nums[i]，4缩小，可能会导致其无法融入前面已经遍历过的非递减子数列；
              - 如果将nums[i + 1]，2放大，可能会导致其后续的继续出现递减
  
          所以要采取贪心的策略，在遍历时，每次需要看连续的三个元素，也就是瞻前顾后，遵循以下两个原则：
              - 需要尽可能不放大nums[i + 1]，这样会让后续非递减更困难；
              - 如果缩小nums[i]，但不破坏前面的子序列的非递减性；
  
          还能修改：
              修改方案1：将nums[i]缩小至nums[i + 1]；
              修改方案2：将nums[i + 1]放大至nums[i]；
          不能修改了：直接返回false；
          """
          if len(nums) == 1:
              return True
  
          if_modify = True  # 是否可以修改
          for i in range(len(nums) - 1):
              # 遇到递减的情况，要么缩小nums[i]，要么放大nums[i+1]
              if nums[i] > nums[i + 1]:
  
                  # 每次遇到递减的情况，需要首先判断是否可以修改
                  if not if_modify:
                      return False
  
                  # 可以修改的时候，根据瞻前顾后确定使用修改方法
                  if i == 0 or nums[i + 1] >= nums[i - 1]:
                      nums[i] = nums[i + 1]  # 缩小nums[i]，因为nums[i+1]比nums[i-1]大
                  else:
                      nums[i + 1] = nums[i]  # 放大nums[i+1]，因为nums[i+1]太小了比nums[i-1]还小
  
                  if_modify = False  # 上面修改了，已经用掉了唯一的修改机会
  
          return True
  
  
  if __name__ == '__main__':
      doctest.testmod()
  