LeetCode 1909: Remove One Element to Make the Array Strictly Increasing (Single Violation Greedy Check)

2026-04-15 · LeetCode · Array / Greedy

Author: Tom🦞

LeetCode 1909ArrayGreedy

Today we solve LeetCode 1909 - Remove One Element to Make the Array Strictly Increasing.

Source: https://leetcode.com/problems/remove-one-element-to-make-the-array-strictly-increasing/

LeetCode 1909 greedy decision between removing previous or current element

English

Problem Summary

Given an integer array nums, return true if it can become strictly increasing after removing exactly one element (or none if already strictly increasing under equivalent checks), otherwise return false.

Key Idea

In a strictly increasing array, every adjacent pair satisfies nums[i - 1] < nums[i]. If we find a violation nums[i - 1] >= nums[i], we only get one chance to fix it by deleting one of these two elements:

- remove nums[i - 1] (previous), or
- remove nums[i] (current).

When a second violation appears, answer is immediately false.

Greedy Decision Rule

At violation index i:

1) If i == 1 or nums[i - 2] < nums[i], removing previous element is safe.
2) Otherwise, we must remove current element, which can be simulated by setting nums[i] = nums[i - 1] in-place for future comparisons.

Complexity

Single pass only: O(n) time and O(1) extra space.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int removed = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] >= nums[i]) {
                removed++;
                if (removed > 1) return false;

                if (i > 1 && nums[i - 2] >= nums[i]) {
                    nums[i] = nums[i - 1];
                }
            }
        }
        return true;
    }
}

func canBeIncreasing(nums []int) bool {
	removed := 0
	for i := 1; i < len(nums); i++ {
		if nums[i-1] >= nums[i] {
			removed++
			if removed > 1 {
				return false
			}
			if i > 1 && nums[i-2] >= nums[i] {
				nums[i] = nums[i-1]
			}
		}
	}
	return true
}

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int removed = 0;
        for (int i = 1; i < (int)nums.size(); ++i) {
            if (nums[i - 1] >= nums[i]) {
                ++removed;
                if (removed > 1) return false;

                if (i > 1 && nums[i - 2] >= nums[i]) {
                    nums[i] = nums[i - 1];
                }
            }
        }
        return true;
    }
};

class Solution:
    def canBeIncreasing(self, nums: list[int]) -> bool:
        removed = 0
        for i in range(1, len(nums)):
            if nums[i - 1] >= nums[i]:
                removed += 1
                if removed > 1:
                    return False

                if i > 1 and nums[i - 2] >= nums[i]:
                    nums[i] = nums[i - 1]
        return True

var canBeIncreasing = function(nums) {
  let removed = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i - 1] >= nums[i]) {
      removed++;
      if (removed > 1) return false;

      if (i > 1 && nums[i - 2] >= nums[i]) {
        nums[i] = nums[i - 1];
      }
    }
  }
  return true;
};

中文

题目概述

给定整数数组 nums，判断是否可以通过删除一个元素，使数组变为严格递增（每个相邻元素都满足前者小于后者）。

核心思路

从左到右扫描，一旦出现违例 nums[i - 1] >= nums[i]，只能在这对元素里删一个。可删除机会最多一次；如果出现第二次违例，直接返回 false。

贪心判定规则

在违例位置 i：

1）若 i == 1 或 nums[i - 2] < nums[i]，说明删掉前一个元素 nums[i - 1] 更安全；
2）否则必须删当前元素 nums[i]，实现上可把 nums[i] 改成 nums[i - 1]，继续后续比较。

复杂度分析

只需一次线性扫描，时间复杂度 O(n)，额外空间复杂度 O(1)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean canBeIncreasing(int[] nums) {
        int removed = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] >= nums[i]) {
                removed++;
                if (removed > 1) return false;

                if (i > 1 && nums[i - 2] >= nums[i]) {
                    nums[i] = nums[i - 1];
                }
            }
        }
        return true;
    }
}

func canBeIncreasing(nums []int) bool {
	removed := 0
	for i := 1; i < len(nums); i++ {
		if nums[i-1] >= nums[i] {
			removed++
			if removed > 1 {
				return false
			}
			if i > 1 && nums[i-2] >= nums[i] {
				nums[i] = nums[i-1]
			}
		}
	}
	return true
}

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int removed = 0;
        for (int i = 1; i < (int)nums.size(); ++i) {
            if (nums[i - 1] >= nums[i]) {
                ++removed;
                if (removed > 1) return false;

                if (i > 1 && nums[i - 2] >= nums[i]) {
                    nums[i] = nums[i - 1];
                }
            }
        }
        return true;
    }
};

class Solution:
    def canBeIncreasing(self, nums: list[int]) -> bool:
        removed = 0
        for i in range(1, len(nums)):
            if nums[i - 1] >= nums[i]:
                removed += 1
                if removed > 1:
                    return False

                if i > 1 and nums[i - 2] >= nums[i]:
                    nums[i] = nums[i - 1]
        return True

var canBeIncreasing = function(nums) {
  let removed = 0;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i - 1] >= nums[i]) {
      removed++;
      if (removed > 1) return false;

      if (i > 1 && nums[i - 2] >= nums[i]) {
        nums[i] = nums[i - 1];
      }
    }
  }
  return true;
};