原文链接: https://leetcode-cn.com/problems/remove-one-element-to-make-the-array-strictly-increasing

英文原文

Given a 0-indexed integer array nums, return true if it can be made strictly increasing after removing exactly one element, or false otherwise. If the array is already strictly increasing, return true.

The array nums is strictly increasing if nums[i - 1] < nums[i] for each index (1 <= i < nums.length).

 

Example 1:

Input: nums = [1,2,10,5,7]
Output: true
Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7].
[1,2,5,7] is strictly increasing, so return true.

Example 2:

Input: nums = [2,3,1,2]
Output: false
Explanation:
[3,1,2] is the result of removing the element at index 0.
[2,1,2] is the result of removing the element at index 1.
[2,3,2] is the result of removing the element at index 2.
[2,3,1] is the result of removing the element at index 3.
No resulting array is strictly increasing, so return false.

Example 3:

Input: nums = [1,1,1]
Output: false
Explanation: The result of removing any element is [1,1].
[1,1] is not strictly increasing, so return false.

Example 4:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is already strictly increasing, so return true.

 

Constraints:

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

中文题目

给你一个下标从 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

通过代码

高赞题解

解题思路

遍历整个数组，直到找到一个递减的数对，此时大的数为k，小的数为k+1：

• 如果k - 1 < 0，说明大的数在开头，删除即可。
• 如果nums[k + 1] > nums[k - 1]，说明下标为k这个大数是驼峰，删除即可保证递增。
• 如果K+ 2 >= n，说明小的数在末尾，删除即可。
• 如果nums[k] < nums[k + 2]，说明下标为k+1这个小数是低谷，删除即可保证递增。

此外，以上判断只需要判断一次，如果进入了第二次判断，说明出现了第二组扰乱递增的数对，直接返回false。

时间复杂度为O(n)，只遍历了一次数组。

代码

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        boolean asc = true;
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] >= nums[i + 1]) {
                if (asc) {
                    if (i - 1 < 0 || nums[i + 1] > nums[i - 1]) asc = false;
                    else if (i + 2 >= n || nums[i + 2] > nums[i]) asc = false;
                    else return false;
                }
                else return false;
            }
        }
        return true;
    }
}

统计信息

通过次数	提交次数	AC比率
5132	15931	32.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言