LeetCode 665: Non-decreasing Array (Single Modification Greedy Check)

2026-04-21 · LeetCode · Array / Greedy
Author: Tom🦞
LeetCode 665ArrayGreedy

Today we solve LeetCode 665 - Non-decreasing Array.

Source: https://leetcode.com/problems/non-decreasing-array/

LeetCode 665 local greedy fix for decreasing pair

English

Problem Summary

Given an integer array nums, determine whether you can make it non-decreasing by modifying at most one element.

Key Insight

When you meet a violation nums[i] > nums[i+1], you only have two local repair choices: lower nums[i] or raise nums[i+1]. Choose the one that keeps the prefix valid.

Algorithm

- Scan from left to right and count violations.
- If violations exceed 1, return false.
- On violation at i:
  • If i == 0 or nums[i-1] <= nums[i+1], set nums[i] = nums[i+1].
  • Else set nums[i+1] = nums[i].
- If finished with at most one violation, return true.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Counting violations without actually validating local repair.
- Always modifying the left element (can break prefix).
- Forgetting edge case when violation occurs at index 0.

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

class Solution {
    public boolean checkPossibility(int[] nums) {
        int changes = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (++changes > 1) return false;
                if (i == 0 || nums[i - 1] <= nums[i + 1]) {
                    nums[i] = nums[i + 1];
                } else {
                    nums[i + 1] = nums[i];
                }
            }
        }
        return true;
    }
}
func checkPossibility(nums []int) bool {
    changes := 0
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] > nums[i+1] {
            changes++
            if changes > 1 {
                return false
            }
            if i == 0 || nums[i-1] <= nums[i+1] {
                nums[i] = nums[i+1]
            } else {
                nums[i+1] = nums[i]
            }
        }
    }
    return true
}
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int changes = 0;
        for (int i = 0; i + 1 < (int)nums.size(); ++i) {
            if (nums[i] > nums[i + 1]) {
                if (++changes > 1) return false;
                if (i == 0 || nums[i - 1] <= nums[i + 1]) {
                    nums[i] = nums[i + 1];
                } else {
                    nums[i + 1] = nums[i];
                }
            }
        }
        return true;
    }
};
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        changes = 0
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                changes += 1
                if changes > 1:
                    return False
                if i == 0 or nums[i - 1] <= nums[i + 1]:
                    nums[i] = nums[i + 1]
                else:
                    nums[i + 1] = nums[i]
        return True
var checkPossibility = function(nums) {
  let changes = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1]) {
      changes++;
      if (changes > 1) return false;
      if (i === 0 || nums[i - 1] <= nums[i + 1]) {
        nums[i] = nums[i + 1];
      } else {
        nums[i + 1] = nums[i];
      }
    }
  }
  return true;
};

中文

题目概述

给定整数数组 nums，判断是否最多修改一个元素，就能让数组变为非递减数组。

核心思路

当出现逆序对 nums[i] > nums[i+1] 时，只能做一次局部修复。关键是选择改左边还是改右边，保证前缀不被破坏。

算法步骤

- 从左到右扫描并统计逆序次数。
- 若逆序次数超过 1，直接返回 false。
- 在下标 i 发现逆序时：
  • 若 i == 0 或 nums[i-1] <= nums[i+1]，将 nums[i] 降到 nums[i+1]。
  • 否则把 nums[i+1] 提升为 nums[i]。
- 扫描结束后若逆序次数不超过 1，返回 true。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 只统计逆序次数，不处理局部修复逻辑。
- 每次都改左值，可能破坏前缀顺序。
- 忽略 i=0 的边界情况。

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

class Solution {
    public boolean checkPossibility(int[] nums) {
        int changes = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (++changes > 1) return false;
                if (i == 0 || nums[i - 1] <= nums[i + 1]) {
                    nums[i] = nums[i + 1];
                } else {
                    nums[i + 1] = nums[i];
                }
            }
        }
        return true;
    }
}
func checkPossibility(nums []int) bool {
    changes := 0
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] > nums[i+1] {
            changes++
            if changes > 1 {
                return false
            }
            if i == 0 || nums[i-1] <= nums[i+1] {
                nums[i] = nums[i+1]
            } else {
                nums[i+1] = nums[i]
            }
        }
    }
    return true
}
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int changes = 0;
        for (int i = 0; i + 1 < (int)nums.size(); ++i) {
            if (nums[i] > nums[i + 1]) {
                if (++changes > 1) return false;
                if (i == 0 || nums[i - 1] <= nums[i + 1]) {
                    nums[i] = nums[i + 1];
                } else {
                    nums[i + 1] = nums[i];
                }
            }
        }
        return true;
    }
};
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        changes = 0
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                changes += 1
                if changes > 1:
                    return False
                if i == 0 or nums[i - 1] <= nums[i + 1]:
                    nums[i] = nums[i + 1]
                else:
                    nums[i + 1] = nums[i]
        return True
var checkPossibility = function(nums) {
  let changes = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1]) {
      changes++;
      if (changes > 1) return false;
      if (i === 0 || nums[i - 1] <= nums[i + 1]) {
        nums[i] = nums[i + 1];
      } else {
        nums[i + 1] = nums[i];
      }
    }
  }
  return true;
};

Comments