IOS 算法(基础篇) ----- 删除一个元素使数组严格递增
给你一个下标从 0 开始的整数数组 nums ，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。
数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。
其中:
2 <= nums.length <= 1000
1 <= nums[i] <= 1000
例子:
输入：nums = [1,2,10,5,7]
输出：true
解释：从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。
[1,2,5,7] 是严格递增的，所以返回 true 。
输入：nums = [2,3,1,2]
输出：false
解释：
[3,1,2] 是删除下标 0 处元素后得到的结果。
[2,1,2] 是删除下标 1 处元素后得到的结果。
[2,3,2] 是删除下标 2 处元素后得到的结果。
[2,3,1] 是删除下标 3 处元素后得到的结果。
没有任何结果数组是严格递增的，所以返回 false 。
输入：nums = [1,1,1]
输出：false
解释：删除任意元素后的结果都是 [1,1] 。
[1,1] 不是严格递增的，所以返回 false 。
示例 4：
输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 已经是严格递增的，所以返回 true 。
解题思路:
遍历法
题意不难, 关键是判断处理, 判断如果没处理好很费时间
- 设置一个判断符号
bool selb(int等能用作判断也行), 主要用于计数是否做一次操作 - 0 ~ nums.count - 1 内 for 循环判断
第一次:
-
如果 "后者大于等于前者" 即:
nums[i] >= nums[i + 1], 不满足严格递增进入判断:
-
nums[i + 1] > nums[i - 1], 即有nums[i] >= nums[i + 1] > nums[i - 1], 例如: [... 9, 11, 10, ...], [... 9, 10, 10, ...]等情况, 需要删除一次, 令selb = false。因为取nums[i - 1], 防止越界, 固需要留意边界 即: [10, 1, 2 ...], [1, 1, 2 ...] 等这种情况。固i - 1 < 0 && nums[i] >= nums[i + 1]单独处理下, 也令selb = false。
-
-
nums[i + 2] > nums[i], 既有nums[i + 2] > nums[i] >= nums[i + 1], 例如: [...10, 9, 11, ...], [...9, 9, 11, ...]等情况, 需要删除一次, 令selb = false。这种情况因为取nums[i + 2], 防止越界, 固需要留意边界 即: [...8, 10, 9], [...8, 10, 10] 等这种情况。固i + 2 == nums.count && nums[i] >= nums[i + 1]单独处理下, 也令selb = false。
- 其他情况直接
false, 例如:
① nums[i + 2] > nums[i + 1] > nums[i], [...3, 2, 1...]
② nums[i + 2] = nums[i + 1] = nums[i], [1, 2, 1]
...
第二次:
- 如果
selb == false第二次进入nums[i] >= nums[i + 1], 表明需要改动1次以上, 直接false返回
其他:
只有1次或者0次, true返回
代码:
func canBeIncreasing(_ nums: [Int]) -> Bool {
var selb = true
for i in 0..<nums.count - 1 {
if nums[i] >= nums[i + 1] {
if selb {
if i - 1 < 0 || nums[i + 1] > nums[i - 1] ||
i + 2 == nums.count || nums[i + 2] > nums[i] {
selb = false
} else { return false; }
} else { return false }
}
}
return true;
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
