解题过程
:::info
题目链接
给你一个长度为 n 的整数数组 nums ,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列
我们是这样定义一个非递减数列的: 对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]
:::
/*** @link https://leetcode.cn/problems/non-decreasing-array/* @title 665. 非递减数列* @description 给你一个长度为 n 的整数数组 nums ,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。* 我们是这样定义一个非递减数列的: 对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]* @param {number[]} nums* @return {boolean}*/// 解法一:// 思路:利用反向思维// 第一步:遍历数组元素值中有一个元素值大于下一个元素值,即i (0 <= i <= n-2), nums[i] > nums[i + 1]就增加改变元素次数值// 第二步:且判断当前元素的前一项元素值是否大于后一项的元素值,是则改变下一个元素值为当前元素值,原因是为了进入判断下一次循环的元素值对比,// 第三步:数组遍历结束后最后判断改变元素次数值是否小于等于1,小于等于1说明数组元素改变1次可以满足非递减数列要求var checkPossibility = function (nums) {let count = 0for (let i = 0; i <= nums.length - 2; i++) {if (nums[i] > nums[i + 1]) {count++if (i > 0 && nums[i - 1] > nums[i + 1]) {nums[i + 1] = nums[i]}}}return count <= 1}// const result = checkPossibility([4, 2, 3]) // true// const result = checkPossibility([4, 2, 1]) // falseconst result = checkPossibility([3, 4, 2, 3]) // false// const result = checkPossibility([1, 1, 1]) // true// const result = checkPossibility([5, 7, 1, 8]) // true// const result = checkPossibility([2, 3, 3, 2, 4]) // trueconsole.log(result)
解题感受
利用反向思维,我只需要统计递减数列的情况次数判断是否大于1即可
一开始卡在了穷举遍历数组所有情况不满足非递减数列的情况,写了半个小时所有各种情况判断,发现leetcode测试用例不通过,因为统计改变元素次数的时候,容易漏掉判断或出现改变元素是只有一次,但是改变了确导致非递减数列了。
然后改变了想法,也是死缠烂打琢磨了好久,突然想到满足递减数列的情况下,还要判断当前上一项元素值是否大于下一项元素值,如果大于情况下把下把当前元素值赋值给下一项元素值,这样可以有效解决跳出循环遍历问题和模拟判断下一项元素进入循环对比,可以避免虽然元素只改变一次,但是数组确非递减数列问题
