LeetCode 665. 非递减数列

Categories:

题目描述
思路分析
1. 解法一：一次修改贪心（推荐）
相似题目

题目描述

✅ 665. 非递减数列

思路分析

解法一：一次修改贪心（推荐）

核心思路：

遍历数组，发现 nums[i] < nums[i-1] 时计数加一。

若 i < 2 或 nums[i] >= nums[i-2]，则下调 nums[i-1]；否则上调 nums[i]。

若修改次数超过 1，则不可能。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                count++;
                if (count > 1) {
                    return false;
                }

                if (i < 2 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }

        return true;
    }
}

func checkPossibility(nums []int) bool {
	count := 0

	for i := 1; i < len(nums); i++ {
		if nums[i] < nums[i-1] {
			count++
			if count > 1 {
				return false
			}

			if i < 2 || nums[i] >= nums[i-2] {
				nums[i-1] = nums[i]
			} else {
				nums[i] = nums[i-1]
			}
		}
	}

	return true
}

相似题目

题目	难度	考察点
674. 最长连续递增序列	简单	贪心
376. 摆动序列	中等	贪心
122. 买卖股票的最佳时机 II	简单	贪心
334. 递增的三元子序列	中等	贪心
121. 买卖股票的最佳时机	简单	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/34740715