题目

给你一个下标从 0 开始的整数数组 nums ，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。

如果数组本身已经是严格递增的，请你也返回 true 。

数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。

示例 1：输入：nums = [1,2,10,5,7] 输出：true

解释：从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。

[1,2,5,7] 是严格递增的，所以返回 true 。

示例 2：输入：nums = [2,3,1,2] 输出：false

解释：[3,1,2] 是删除下标 0 处元素后得到的结果。

[2,1,2] 是删除下标 1 处元素后得到的结果。

[2,3,2] 是删除下标 2 处元素后得到的结果。

[2,3,1] 是删除下标 3 处元素后得到的结果。

没有任何结果数组是严格递增的，所以返回 false 。

示例 3：输入：nums = [1,1,1] 输出：false

解释：删除任意元素后的结果都是 [1,1] 。

[1,1] 不是严格递增的，所以返回 false 。

示例 4：输入：nums = [1,2,3] 输出：true

解释：[1,2,3] 已经是严格递增的，所以返回 true 。

提示：2 <= nums.length <= 1000

1 <= nums[i] <= 1000

解题思路分析

1、遍历；时间复杂度O(n)，空间复杂度O(n)

func canBeIncreasing(nums []int) bool {
   for i := 0; i < len(nums)-1; i++ {
      if nums[i] >= nums[i+1] {
         return judge(nums, i) == true || judge(nums, i+1) == true
      }
   }
   return true
}

func judge(nums []int, index int) bool {
   arr := append([]int{}, nums[:index]...)
   arr = append(arr, nums[index+1:]...)
   for i := 0; i < len(arr)-1; i++ {
      if arr[i] >= arr[i+1] {
         return false
      }
   }
   return true
}

2、暴力法；时间复杂度O(n^2)，空间复杂度O(n)

func canBeIncreasing(nums []int) bool {
   for i := 0; i < len(nums); i++ {
      if judge(nums, i) == true {
         return true
      }
   }
   return false
}

func judge(nums []int, index int) bool {
   arr := append([]int{}, nums[:index]...)
   arr = append(arr, nums[index+1:]...)
   for i := 0; i < len(arr)-1; i++ {
      if arr[i] >= arr[i+1] {
         return false
      }
   }
   return true
}

3、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func canBeIncreasing(nums []int) bool {
   n := len(nums)
   dp := make([]int, n)
   res := 1
   for i := 0; i < n; i++ {
      dp[i] = 1
      for j := 0; j < i; j++ {
         if nums[j] < nums[i] {
            dp[i] = max(dp[j]+1, dp[i])
         }
      }
      res = max(res, dp[i])
   }
   return res == n || res == n-1
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Easy题目，多种解题方式