What is the pattern for solving the Non-decreasing Array problem?

The problem follows an array-driven solution strategy, focusing on identifying violations and making minimal modifications.

How can I determine if modifying one element is enough to solve the Non-decreasing Array problem?

You need to track any violations where `nums[i] > nums[i + 1]` and check if modifying the current or next element resolves the issue without introducing new violations.

How do I handle edge cases for the Non-decreasing Array problem?

If there are multiple violations in the array, return `false` immediately, as modifying just one element will not be sufficient.

Can multiple modifications be allowed in the Non-decreasing Array problem?

This problem specifically requires at most one modification. Allowing more modifications would change the problem's constraints and solution approach.

What is the time complexity of the Non-decreasing Array problem?

The time complexity is O(n) due to the need for a single pass through the array.

#665

Medium

auto_awesome数组·driven

LeetCode 题解工作台

非递减数列

给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的：对于数组中任意的 i (0 ，总满足 nums[i] 。示例 1: 输入: nums = [4,2,3] 输出: true 解释: 你可以通过把…

数组

题目描述

给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的：对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

提示：

n == nums.length
1 <= n <= 10⁴
-10⁵ <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：两次遍历

在最多改变一个元素的情况下，若要将数组变成非递减数列，那么数组最多只能有一个位置，其左右两侧的元素不满足非递减数列的要求。也即数组中只会存在一个位置 $i$ ，使得 $nums[i] \gt nums[i+1]$ 。

因此，我们可以从左到右遍历数组，找到第一个不满足非递减数列要求的位置 $i$ ，然后将 $nums[i]$ 修改为 $nums[i+1]$ 或者将 $nums[i+1]$ 修改为 $nums[i]$ ，再判断修改后的数组是否满足非递减数列的要求。如果满足，则返回 true，否则返回 false。

遍历结束后，如果没有找到不满足非递减数列要求的位置，说明数组本身就是非递减数列，返回 true。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        def is_sorted(nums: List[int]) -> bool:
            return all(a <= b for a, b in pairwise(nums))

        n = len(nums)
        for i in range(n - 1):
            a, b = nums[i], nums[i + 1]
            if a > b:
                nums[i] = b
                if is_sorted(nums):
                    return True
                nums[i] = nums[i + 1] = a
                return is_sorted(nums)
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for candidates who can correctly identify and handle violations in the array.
question_mark
Evaluate if the candidate is able to make decisions based on a single modification possibility.
question_mark
Pay attention to the candidate’s approach towards edge cases like multiple violations.

warning

常见陷阱

外企场景

error
Assuming that one modification always solves the problem, without verifying the array after modification.
error
Not handling the case where multiple violations are found, leading to incorrect results.
error
Over-complicating the solution by introducing unnecessary data structures or operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to allow up to two modifications and check how the candidate handles this.
arrow_right_alt
Introduce larger arrays to see how the candidate optimizes for larger inputs.
arrow_right_alt
Change the array to be a non-negative integer array, modifying the problem constraints.

help

常见问题

外企场景

继续练习

#667 优美的排列 II #661 图片平滑器 #659 分割数组为连续子序列