本文主要是介绍【第0005页 · 贪心】非递减数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【前言】本文以及之后的一些题解都会陆续整理到目录中，若想了解全部题解整理，请看这里：
第0005页 · 非递减数列
今天我们来看一道 LeetCode 上“广泛好评”的一道 Easy 题！！！（蓝色是 OJ 平台）
【非递减数列】 给你一个长度为 n 的整数数组 nums。请你判断在最多改变 1 个元素的情况下，该数组能否变为一个非递减数列。我们是这样定义一个非递减数列的：对数组中任意一个 i，总满足 nums[i] <= nums[i + 1]。
IO要求 示例 输入描述：
提供一个 vector 数组
nums = [4,3,2,3] 输出描述：
给出判断 true 或 false
false
由于这是在 LeetCode 上，它已经给出了要求的格式，这里我们也就写出一个满足要求的和函数即可。
【解题分析】首先， 本题的要求是维持一个一个非递减的数列，所以遇到递减的情况时（nums[i] > nums[i + 1]），要么将前面的元素缩小，要么将后面的元素放大。
但是，如果将nums[i]缩小，可能会导致其无法融入前面已经遍历过的非递减子数列；如果将nums[i + 1]放大，可能会导致其后续的继续出现递减。
所以要采取贪心的策略，在遍历时，每次需要看连续的三个元素，也就是瞻前顾后，遵循以下两个原则：1、需要尽可能不放大nums[i + 1]，因为这样会让后续非递减更困难；2、
如果缩小nums[i]，需要不能破坏前面的子序列的非递减性。
【源码展示】
class Solution { public:bool checkPossibility(vector<int>& nums) {int len = nums.size();bool flag = nums[0] <= nums[1] ? true : false; // 定义能否进行修改for (int i = 1; i < len - 1; i++) {if (nums[i] > nums[i + 1]) { // 如果出现递减if (flag) { // 如果还可以修改// 使用修改方案1if (nums[i + 1] >= nums[i - 1]) nums[i] = nums[i + 1]; // 使用修改方案2else nums[i + 1] = nums[i];flag = false;}else return false;}}return true;} };
这篇关于【第0005页 · 贪心】非递减数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
