Android 刷脸支付 分布式机器 LeetCode 全局重载运算符 Nginx RabbitMQ image web vector vuejs2 ssis Component Keys.js vue框架 jquery通过class获取元素 jquery获取兄弟节点 python中count java队列 java编程学习入门 java文件写入 java文档 java中float java新建文件 java时间转时间戳 tmac修改器 千千静听绿色版 按钮制作 python输入数字 咪咕客户端下载 丁丁下载 vbs表白代码 迅雷免费会员号共享 滑动门代码 战斗的召唤 博途v14安装教程 手机电脑模拟器 wegame更新失败 php递归 edquota
当前位置: 首页 > 学习教程  > python

Leetcode每日一题:665. 非递减数列

2021/2/8 10:44:08 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

目录问题描述思路分析及代码实现问题描述 给你一个长度为 n 的整数数组&#xff0c;请你判断在 最多 改变 1 个元素的情况下&#xff0c;该数组能否变成一个非递减数列。 我们是这样定义一个非递减数列的&#xff1a; 对于数组中所有的 i (0 < i < n-2)&#xff0c;总满…

目录

    • 问题描述
    • 思路分析及代码实现

问题描述

给你一个长度为 n 的整数数组,请你判断在 最多 改变 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
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明:

  • 1 <= n <= 10 ^ 4
  • 10 ^ 5 <= nums[i] <= 10 ^ 5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/non-decreasing-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路分析及代码实现

首先可以想到的是通过计数判断后面数比前面数小的有几个,如果大于1就返回False
当nums[i] > nums[i+1]时,这时候可以有两种操作:
1.将nums[i]降为nums[i+1],这是必须保证nums[i-1] <= nums[i+1],否则无法改变局部递减
2.将nums[i+1]升为nums[i],这种做法一定可以该边局部的增减性,但是对后面的值也有影响
所以可以优先考虑第一种操作,使得前i+2个数一定时非递增的,然后不满足的再考虑操作二

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        num = 0
        n = len(nums)
        for i in range(n-1):
            if nums[i] > nums[i+1]:
                num += 1
                if num > 1:
                    return False
                if i == 0:
                    nums[i] = nums[i+1]
                else:
                    if nums[i-1] <= nums[i+1]:
                        nums[i] = nums[i+1]
                    else:
                        nums[i+1] = nums[i]
        return True

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000297.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?