[Swift]LeetCode665. 非递减数列 | Non-decreasing Array_app

概述Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element. We define an array is non-decreasing if array[i] <= array[i + 1] holds for every @H_403_2@

Given an array with n integers,your task is to check if it Could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

input: [4,2,3]Output: TrueExplanation: You Could modify the first  to  to get a non-decreasing array. 41

Example 2:

input: [4,1]Output: FalseExplanation: You can‘t get a non-decreasing array by modify at most one element.

Note: The n belongs to [1,10,000].

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的：对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

示例 1:

输入: [4,3]输出: True解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

输入: [4,1]输出: False解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明: n 的范围为 [1,000]。

44ms

 1 class Solution { 2     func checkPossibility(_ nums: [Int]) -> Bool { 3         var i = 0 4         var j = nums.count - 1 5         while i < j && nums[i] <= nums[i+1] { 6             i += 1 7         } 8         while i < j && nums[j] >= nums[j-1] { 9             j -= 110         }11         let head = (i == 0) ? Int.min : nums[i-1]12         let next = (j == nums.count - 1) ? Int.max : nums[j+1]13         14         if j - i <= 1 && (head < nums[j] || nums[i] < next) {15             return true16         } else {17             return false18         }19     }20 }

188ms

 1 class Solution { 2     func checkPossibility(_ nums: [Int]) -> Bool { 3          4         if nums.count < 3 { 5             return true 6         } 7          8         var i = 0 9         10         while i <= nums.count - 2,nums[i] <= nums[i + 1] {11             i += 112         }13         14         var j = nums.count - 115         16         if i >= j - 1 {17             return true18         }19         20         while 1 <= j,nums[j - 1] <= nums[j] {21             j -= 122         }23         24         if j <= 1  {25             return true26         }27         28         return ((j - i == 2) && (nums[i] <= nums[j])) 29                || 30                ((j - i == 1) 31                    && 32                    ((0 < i) && (nums[i - 1] <= nums[j])33                    || ((j < nums.count - 1) && (nums[i] <= nums[j + 1]))))34     }35 }

Runtime: 192 ms Memory Usage: 19.5 MB

 1 class Solution { 2     func checkPossibility(_ nums: [Int]) -> Bool { 3         var nums = nums 4         var cnt:Int = 1 5         var n:Int = nums.count 6         for i in 1..<n 7         { 8             if nums[i] < nums[i - 1] 9             {10                 if cnt == 0 {return false}11                 if i == 1 || nums[i] >= nums[i - 2]12                 {13                     nums[i - 1] = nums[i]14                 }15                 else16                 {17                     nums[i] = nums[i - 1]18                 }19                 cnt -= 120             }21         }22         return true23     }24 }

196ms

 1 class Solution { 2     func checkPossibility(_ nums: [Int]) -> Bool { 3             var c = 0 4             var nums = [-Int.max] + nums 5             var low = nums[0] 6          7         for (i,n) in nums.enumerated().dropFirst() { 8             if n < nums[i-1] { 9                 if n >= low {10                     nums[i-1] = low11                 } else {12                     nums[i] = nums[i-1]13                 }14                 c += 115                 if c > 1 {16                     return false17                 }18             }19             if i > 1 {20                 low = nums[i-1]21             }22         }23         24         return true25     }26 }

200ms

 1 class Solution { 2     func checkPossibility(_ nums: [Int]) -> Bool { 3         var newNums = nums 4         if newNums.count <= 2 { 5             return true 6         } 7          8         var i = 1 9         var j = 210         var noOfChange = 011         12         if (newNums[i] < newNums[i-1]) {13             newNums[i-1] = newNums[i]14             noOfChange = noOfChange + 115         }16         17         while j <= newNums.count - 1 {18             if (newNums[i] > newNums[j]) {19                 //if [j] > [i-1],change value of [i] -> [i-1] 20                 if (newNums[j] > newNums[i-1]) {21                     newNums[i] = newNums[i-1]22                 } 23                 //else,change [j] -> [i]24                 else { 25                     newNums[j] = newNums[i]26                 }27                 28                 noOfChange = noOfChange + 129             }30             j = j + 131             i = i + 132         }33         34         return noOfChange <= 135     }36 }

208ms

 1 class Solution { 2     func checkPossibility(_ nums: [Int]) -> Bool { 3          4         if nums.count < 3 { 5             return true 6         } 7          8         var index = -1 9         10         for i in 0 ..< (nums.count - 1) {11             if nums[i] > nums[i+1] {12                 if index != -1 { return false }13                 index = i14             }15         }16         17         return ((index == -1)18             || (index == 0)19             || (index == nums.count - 2)20             || (nums[index+1] - nums[index-1] > 0)21             || (nums[index+2] - nums[index] > 0))22     }23 }

284ms

 1 class Solution { 2     func checkPossibility(_ nums: [Int]) -> Bool { 3         guard nums.count > 1 && nums.count <= 10000 else { 4             return nums.count == 1 5         } 6         var array = nums 7         var modifIEd = false 8         for i in 0 ..< array.count - 1 { 9             if array[i] > array[i + 1] {10                 if modifIEd {11                     return false12                 }13                 if i > 0 && array[i - 1] > array[i + 1] {14                     array[i + 1] = array[i]15                 }16                 modifIEd = true17             }18         }19         return true20     }21 }