Question

1909. Remove One Element to Make the Array Strictly Increasing

中文文档

Description

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.

 

Constraints:

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

Solutions

Solution 1

class Solution:
  def canBeIncreasing(self, nums: List[int]) -> bool:
    def check(nums, i):
      prev = -inf
      for j, num in enumerate(nums):
        if i == j:
          continue
        if prev >= nums[j]:
          return False
        prev = nums[j]
      return True

    i, n = 1, len(nums)
    while i < n and nums[i - 1] < nums[i]:
      i += 1
    return check(nums, i - 1) or check(nums, i)

class Solution {
  public boolean canBeIncreasing(int[] nums) {
    int i = 1, n = nums.length;
    for (; i < n && nums[i - 1] < nums[i]; ++i)
      ;
    return check(nums, i - 1) || check(nums, i);
  }

  private boolean check(int[] nums, int i) {
    int prev = Integer.MIN_VALUE;
    for (int j = 0; j < nums.length; ++j) {
      if (i == j) {
        continue;
      }
      if (prev >= nums[j]) {
        return false;
      }
      prev = nums[j];
    }
    return true;
  }
}

class Solution {
public:
  bool canBeIncreasing(vector<int>& nums) {
    int i = 1, n = nums.size();
    for (; i < n && nums[i - 1] < nums[i]; ++i)
      ;
    return check(nums, i - 1) || check(nums, i);
  }

  bool check(vector<int>& nums, int i) {
    int prev = 0;
    for (int j = 0; j < nums.size(); ++j) {
      if (i == j) continue;
      if (prev >= nums[j]) return false;
      prev = nums[j];
    }
    return true;
  }
};

func canBeIncreasing(nums []int) bool {
  i, n := 1, len(nums)
  for ; i < n && nums[i-1] < nums[i]; i++ {

  }
  return check(nums, i-1) || check(nums, i)
}

func check(nums []int, i int) bool {
  prev := 0
  for j := 0; j < len(nums); j++ {
    if i == j {
      continue
    }
    if prev >= nums[j] {
      return false
    }
    prev = nums[j]
  }
  return true
}

function canBeIncreasing(nums: number[]): boolean {
  const check = (p: number) => {
    let prev = undefined;
    for (let j = 0; j < nums.length; j++) {
      if (p != j) {
        if (prev !== undefined && prev >= nums[j]) {
          return false;
        }
        prev = nums[j];
      }
    }
    return true;
  };
  for (let i = 0; i < nums.length; i++) {
    if (nums[i - 1] >= nums[i]) {
      return check(i - 1) || check(i);
    }
  }
  return true;
}

impl Solution {
  pub fn can_be_increasing(nums: Vec<i32>) -> bool {
    let check = |p: usize| -> bool {
      let mut prev = None;
      for j in 0..nums.len() {
        if p != j {
          if let Some(value) = prev {
            if value >= nums[j] {
              return false;
            }
          }
          prev = Some(nums[j]);
        }
      }
      true
    };
    for i in 1..nums.len() {
      if nums[i - 1] >= nums[i] {
        return check(i - 1) || check(i);
      }
    }
    true
  }
}