删除一个元素使数组严格递增

5780. 删除一个元素使数组严格递增

难度简单3

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

通过次数2,174

提交次数6,917

单调队列

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < n; i++) {
            if (deque.isEmpty()) deque.offerLast(nums[i]);
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.offerLast(nums[i]);
            }
        }
        if (n - deque.size() <= 1) return true;
        deque = new LinkedList<Integer>();
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            while (!deque.isEmpty() && deque.peekLast() >= nums[i]) {
                cnt++;
                deque.pollLast();
            }
            deque.offerLast(nums[i]);
        }
        return cnt <= 1;
    }
}

峰与谷

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;
    }
}

双栈模拟

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int n = nums.length;

        // 第一个栈模拟 "pre >= cur 时，删除 pre" 的情况
        Deque<Integer> dq1 = new LinkedList<>() {{
            offerLast(nums[0]);
        }};

        // 第二个栈模拟 "pre >= cur 时，删除 cur" 的情况
        Deque<Integer> dq2 = new LinkedList<>() {{
            offerLast(nums[0]);
        }};
        
        // cnt1、cnt2 各自记录栈1、栈2模拟情况下删除的次数
        // 删除次数>1时，已经不符合题意，直接返回false即可
        int cnt1 = 0, cnt2 = 0;

        for (int i = 1; i < n; i++) {
            int x = nums[i];

            while (!dq1.isEmpty() && dq1.peekLast() >= x) {
                dq1.pollLast();
                cnt1++;
            }
            dq1.offerLast(x);

            if (dq2.isEmpty() || dq2.peekLast() < x) {
                dq2.offerLast(x);
            } else {
                cnt2++;
            }

            if (cnt1 > 1 && cnt2 > 1) return false;
        }

        return true;
    }
}

作者：echofzoe
链接：https://leetcode-cn.com/problems/remove-one-element-to-make-the-array-strictly-increasing/solution/javashuang-zhan-mo-ni-by-echofzoe-o1vq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信