leetcode 665. Non-decreasing Array

刺骨的言语ヽ痛彻心扉 2022-06-08 04:20 100阅读 0赞

# 1.题目 #

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.  
We define an array is non-decreasing if array\[i\] <= array\[i + 1\] holds for every i (1 <= i < n).

给出一个数组，判断是否能够只改变一个元素使这个数组变为非递减数组。 array\[i\] <= array\[i + 1\]，i属于\[1，n)  
Example 1:  
Input: \[4,2,3\]  
Output: True  
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.  
Example 2:  
Input: \[4,2,1\]  
Output: False  
Explanation: You can’t get a non-decreasing array by modify at most one element.  
Note: The n belongs to \[1, 10,000\].

# 2.分析 #

一次遍历数组，用计数器count记录出现不符合a\[i\] <= a\[i + 1\]的次数

出现第一次时，如果此时位置为i，即 a\[i-1\] > a\[i\],此时需要改变一个元素的值，使其符合非递减的规则。  
判断:  
如果i==1 或者 a\[i-2\]<=a\[i\]，则令 a\[i-1\]=a\[i\] 那么就是 a\[i-2\]

# 3.代码 #

class Solution {
    public:
        bool checkPossibility(vector<int>& nums) {
            int count = 0;
            for (int i = 1; i < nums.size()&&count<2; i++) {
                if (nums[i] < nums[i - 1]) {
                    if (i == 1 || nums[i - 2] <= nums[i])
                        nums[i - 1] = nums[i];
                    else
                        nums[i] = nums[i - 1];
                    count += 1;
                }
    
            }
            return count < 2;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，100人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_贪心算法_中等_665.非递减数列

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 1 个元素的情况下

比眉伴天荒/ 2023年10月06日 23:43/ 0 赞/ 14 阅读

相关 leetcode 665.非递减数列

[https://leetcode-cn.com/problems/non-decreasing-array/submissions/][https_leetcode-cn.c

﹏ヽ暗。殇╰゛Y/ 2023年08月17日 17:01/ 0 赞/ 115 阅读

相关（js）leetcode 665. 非递减数列

题目： > 给你一个长度为 n 的整数数组，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。 > > 我们是这样定义一个非递减数列的：对于数

我会带着你远行/ 2022年10月31日 05:23/ 0 赞/ 143 阅读

相关 LeetCode 665. 非递减数列

给你一个长度为 n 的整数数组，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的：对于数组中所有的 i (0 <=

蔚落/ 2022年10月29日 03:11/ 0 赞/ 158 阅读

相关 leetcode 665. Non-decreasing Array

1.题目 Given an array with n integers, your task is to check if it could become non-dec

刺骨的言语ヽ痛彻心扉/ 2022年06月08日 04:20/ 0 赞/ 101 阅读

相关 leetcode 665. Non-decreasing Array 不递减数组 + 注意区分情况 + 网易游戏编程题

Given an array with n integers, your task is to check if it could become non-decreasing

迈不过友情╰/ 2022年06月03日 07:24/ 0 赞/ 85 阅读

相关 665. Non-decreasing Array

题目描述：给定一个有n个整数的数组，检查它是否可以通过修改最多一个元素使它变得非递减数组 Given an array with n integers, your

拼搏现实的明天。/ 2022年06月03日 05:52/ 0 赞/ 113 阅读

相关 Leetcode 665 (高级编程技术 week8-2)

Leetcode 665 题目描述 Given an array with n integers, your task is to check if it coul

￡神魔★判官ぃ/ 2022年05月26日 13:36/ 0 赞/ 160 阅读

相关 LeetCode-665. 非递减数列

[665. 非递减数列][665.] 给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非

谁借莪１个温暖的怀抱￠/ 2022年04月24日 09:32/ 0 赞/ 176 阅读

相关 LeetCode : 665. Non-decreasing Array 修改一个位置使得数组非递减

试题 Given an array with n integers, your task is to check if it could become non-decrea

小灰灰/ 2021年06月24日 16:10/ 0 赞/ 349 阅读