jjzjj

leetcode 665. Non-decreasing Array 非递减数列(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 贪心

https://leetcode.cn/problems/non-decreasing-array

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

提示：

  • n == nums.length
  • 1 <= n <= 104
  • -105 <= nums[i] <= 105

二、解题思路

最多只有一次修改某个数字的机会，问能否将数组变为非递减数组。举例

例1:4，** 2**， 3

例2:-1， 4， 2， 3

例3:2， 3， 3，** 2**， 4
当后面的数字小于前面的数字后，例如例1中的2小于4，这时可以将修改前面的数字将4修改为2或修改后面的数字将2改为4。我们需要找到这个规律，判断修改哪个数字其实跟再前面的一个数大小有关系：

如果再前面的数不存在，例1中，4前面没有数字了我们直接修改前面的数字为当前数字2即可；

如果再前面的数字存在，并且小于当前数字时，例2中，我们需要修改前面的数字4为当前数字2；

如果再前面的数字存在，且大于当前数，例3中，我们需要修改当前数字2为前面的数3。

由于只有一次修改的机会，所以用一个变量cnt，初始化为1，修改数字后cnt自减1，当下次再需要修改时，如果cnt为0，直接返回false。遍历结束后返回true。

三、解题方法

3.1 Java实现

public class Solution {
    public boolean checkPossibility(int[] nums) {
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (cnt == 0) {
                    return false;
                }
                cnt--;
                if (i == 1) {
                    nums[i - 1] = nums[i];
                } else if (nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        return true;
    }
}

四、总结小记

  • 2022/7/31 今天天气很闷热呀
Non-decreasingdecreasingnumsstrong解题算法与数据结构

有关leetcode 665. Non-decreasing Array 非递减数列(中等)的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  3. 【第37天】斐波那契数列与爬楼梯 | 迭代的鼻祖，递推与记忆化 - 2

    本文已收录于专栏?《Java入门一百例》?学习指引序、专栏前言一、递推与记忆化二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题1】1、题目描述2.解题思路3、模板代码4、代码解析5、原题链接三、推荐专栏四、课后习题序、专栏前言  本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习

  4. ruby - 如何在 Ruby 中为所有可能的值递增/递减一个字符？ - 2

    我有一个长度为一个字符的字符串，可以是任何可能的字符值:irb(main):001:0>"\x0"=>"\u0000"我认为这可能有效:irb(main):002:0>"\x0"+=1SyntaxError:(irb):2:syntaxerror,unexpectedtOP_ASGN,expecting$end"\x0"+=1^from/opt/rh/ruby193/root/usr/bin/irb:12:in`'但是，如您所见，事实并非如此。我怎样才能增加/减少我的角色？编辑:Ruby似乎没有被设置为执行此操作。也许我正在以错误的方式接近这个。我想根据8位block来操作原始数据。我

  5. ruby-on-rails - ruby rails : Unit Testing non activerecord models and still load fixtures - 2

    我可能遗漏了一些东西，但我陷入了这种情况:我有一个非activerecord模型，我想对其进行测试。我从Test::Unit::TestCase派生了它的测试用例类。但是，模型的测试用例类在其自身内部使用了其他activerecord模型类，我想为它们加载固定装置。我的问题是fixtures类方法仅在我从ActiveSupport::TestCase继承测试用例类时才可用(它在ActiveRecord::TestFixtures包含在ActiveSupport::TestCase中)。任何帮助，因为运行测试都会给我错误:未定义的方法“fixtures”(这是可以理解的)，如果我从Act

  6. ruby - 错误 "non-absolute home"通过网络 :SSH - 2

    有问题的代码Net::SSH.start('servername','user')这将返回“非绝对主页”。“用户”实际上有一个主目录。一种建议的方法是使用IdentityFile的完整路径修改~/.ssh/config。这并没有解决问题。其中最疯狂的部分是，如果通过irb或控制台调用，代码可以正常工作。当我们尝试从类方法(使用相同的代码)中调用它时，它会返回“非绝对主页”错误。“用户”也可以通过命令行ssh进入服务器而不会出现问题。服务器正在运行Ubuntu。更新感谢@Phrogz-解决方法是将ENV['HOME']设置为'/home/deploy'。但是，我还没有弄清楚为什么$HOM

  7. ruby-on-rails - Rails 和 attr_accessible : is there a way to raise an exception if a non-mass-assignable attribute is mass-assigned? - 2

    如果尝试批量分配attr_accessible不允许的属性，是否有办法让Rails引发错误？这在开发中会很方便，可以提醒我为什么我Shiny的新模型不起作用，也有助于登录生产环境以检测恶意事件。我正在使用Rails2.3.8，但可能很快就会迁移到3。 最佳答案 从Rails3.2开始，这不再需要monkeypatching——rails现在提供了这种行为。将其放入development.rb和test.rb:config.active_record.mass_assignment_sanitizer=:strict

  8. ruby-on-rails - 弃用警告 : Dangerous query method (method whose arguments are used as raw SQL) called with non-attribute argument(s) - 2

    我将我的Rails5.1.4应用更新到了5.2.0。我的一个模型中有以下范围:scope:by_category,lambda{|category_slug|category_ids=Category.find_by(slug:category_slug)&.subtree_idswhere(category_id:category_ids)}由于该范围，Rails返回以下错误:DEPRECATIONWARNING:Dangerousquerymethod(methodwhoseargumentsareusedasrawSQL)calledwithnon-attributeargume

  9. ruby - 表示 "at least one non-digit"的正则表达式 - 2

    我想根据这个模式验证用户名:允许的字符:字母、数字、连字符、下划线第一个字符必须是字母或数字用户名不能全是数字这个正则表达式满足上面的1和2，但是我想不通如何满足3:/^[a-zA-Z\d][\w\-]+$/(我正在使用Ruby，如果相关的话) 最佳答案 不是很高效，但是很简单:/^(?!\d+$)[a-zA-Z\d][\w\-]+$/前瞻只是意味着:“后面不是一串数字，一直持续到最后”。 关于ruby-表示"atleastonenon-digit"的正则表达式，我们在StackOver

  10. ruby-on-rails - 重定向到某个页面而不是 :notice when non-confirmed user logs in - 2

    如何将登录到特定页面的未确认用户重定向到某个页面而不是显示:notice(“您必须确认您的帐户”)。使用Devisegem(最新)这个问题:(Devise-Redirectedtopageifaccountisn'tconfirmed)提供了这个解决方案:#config/initializers/my_strategy.rbWarden::Strategies.add(:my_strategy)dodefvalid?trueenddefauthenticate!u=User.find_for_authentication(:email=>params[:email])ifu.nil?|

随机推荐