LeetCode——数组Array(15)：贪心算法

答案：可以通过贪心算法判断数组是否能在最多改变1个元素的情况下变成非递减数列。具体步骤如下：

初始化计数器：记录需要修改的次数。
遍历数组：检查每个元素是否满足非递减条件（nums[i] <= nums[i+1]）。
处理递减情况：
如果修改次数已超过1次，直接返回false。
否则，根据前后元素关系决定修改策略：
若nums[i+1] >= nums[i-1]（或i=0），将nums[i]缩小至nums[i+1]（无需实际修改，仅标记）。
否则，将nums[i+1]放大至nums[i]（需实际修改以避免后续冲突）。
返回结果：若遍历结束修改次数不超过1次，返回true。

代码解析方法一：标记修改次数（推荐）def checkPossibility(nums: List[int]) -> bool: d_num = 0 for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: d_num += 1 if d_num > 1: return False if i > 0 and nums[i + 1] < nums[i - 1]: nums[i + 1] = nums[i] # 实际修改nums[i+1] return True方法二：双策略判断（逻辑更清晰）def checkPossibility(nums: List[int]) -> bool: flag = True # 标记是否还能修改 for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: if not flag: return False if i == 0 or nums[i + 1] >= nums[i - 1]: flag = False # 缩小nums[i]（无需修改数组） else: nums[i + 1] = nums[i] # 放大nums[i+1] flag = False return True关键点说明

贪心策略：
优先修改nums[i+1]（放大），因为缩小nums[i]可能破坏前面的非递减性。
仅在nums[i+1] < nums[i-1]时修改nums[i+1]，否则仅标记修改次数。
边界处理：
当i=0时，直接缩小nums[0]（无需检查nums[i-1]）。
修改后需继续遍历，确保后续元素满足条件。
复杂度：
时间复杂度：O(n)，仅需一次遍历。
空间复杂度：O(1)，仅使用常数空间。

示例验证

示例1：[4,2,3]
遇到4>2时，nums[2] < nums[0]不成立，故将nums[1]改为4（实际修改），后续检查通过，返回true。
示例2：[4,2,1]
第一次4>2时修改nums[1]为4，数组变为[4,4,1]；第二次4>1时无法再修改，返回false。

总结

通过贪心算法在遍历中动态选择最优修改策略，确保最多修改一次即可满足非递减条件。核心在于前瞻后顾（检查nums[i-1]与nums[i+1]的关系）以决定修改方向。

您可能感兴趣问答

Collapsible

热门标签

热点问答