打卡力扣题目七

简介: 打卡力扣题目七

关于 ARTS 的释义 —— 每周完成一个 ARTS:

● Algorithm: 每周至少做一个 LeetCode 的算法题

● Review: 阅读并点评至少一篇英文技术文章

● Tips: 学习至少一个技术技巧

● Share: 分享一篇有观点和思考的技术文章


希望通过此次活动能聚集一波热爱技术的人,延续好奇、探索、实践、分享的精神。


一、题目

给你一个长度为 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

解释: 你不能在只改变一个元素的情况下将其变为非递减数列。


二、解题方法一

def checkPossibility(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            # 如果当前元素比下一个元素大,则需要将当前元素减小或将下一个元素增大
            # 为了只改变一个元素,我们可以将当前元素减小到比下一个元素小的最小值
            # 或者将下一个元素增大到比当前元素大的最小值
            # 因此,我们只需要找到这两个数中的最小值即可
            return min(nums[i], nums[i + 1]) < max(nums[i], nums[i + 1])
    # 如果所有元素都满足非递减的条件,则返回 True
    return True

这段代码实现了一个函数 `checkPossibility`,用于判断在最多改变 1 个元素的情况下,给定的整数数组是否能变成一个非递减数列。


函数的输入参数为一个整数数组 `nums`。


首先,我们使用一个循环遍历数组中的每个元素 `i`,并检查当前元素 `nums[i]` 是否比下一个元素 `nums[i + 1]` 大。如果是,则说明当前元素需要被修改,以使得整个数组能够变成非递减数列。


为了只改变一个元素,我们可以将当前元素 `nums[i]` 减小到比下一个元素 `nums[i + 1]` 小的最小值,或者将下一个元素 `nums[i + 1]` 增大到比当前元素 `nums[i]` 大的最小值。因此,我们只需要找到这两个数中的最小值即可。


具体来说,我们可以使用 Python 内置函数 `min()` 来找到两个数中的最小值。如果这个最小值小于等于另一个数,则说明它们可以相等,即不需要进行任何操作;否则,我们需要将较小的那个数减小到等于较大的那个数。


最后,如果所有元素都满足非递减的条件,则返回 True;否则,返回 False。


三、解题方法二

另一种解决方法是使用双指针法。具体来说,我们可以定义两个指针 `left` 和 `right`,分别指向数组的开头和结尾。然后,我们从左到右遍历数组中的每个元素,并检查当前元素是否小于等于右边的元素。如果是,则说明当前元素需要被修改,以使得整个数组能够变成非递减数列。


为了只改变一个元素,我们可以将当前元素 `nums[i]` 减小到比右边的元素 `nums[j]` 小的最小值,或者将右边的元素 `nums[j]` 增大到比当前元素 `nums[i]` 大的最小值。因此,我们只需要找到这两个数中的最小值即可。


具体来说,我们可以使用双指针法来实现这个算法。首先,我们将 `left` 指针指向数组的第一个元素,将 `right` 指针指向数组的最后一个元素。然后,我们从左到右遍历数组中的每个元素 `i`,并检查当前元素是否小于等于右边的元素 `nums[j]`。如果是,则说明当前元素需要被修改,我们需要移动 `left` 指针到下一个位置,并更新左边的最小值;否则,我们需要移动 `right` 指针到前一个位置,并更新右边的最小值。最后,如果所有元素都满足非递减的条件,则返回 True;否则,返回 False。


这个算法的时间复杂度为 O(n),其中 n 为数组的长度。

def checkPossibility(nums):
    left, right = 0, len(nums) - 1
    for i in range(len(nums)):
        while left < right and nums[left] > nums[i]:
            # 如果左边的元素比当前元素大,则将左边的指针向右移动一位
            left += 1
        while left < right and nums[right] < nums[i]:
            # 如果右边的元素比当前元素小,则将右边的指针向左移动一位
            right -= 1
        if left >= right:
            # 如果左边的指针已经到达了数组的末尾,说明无法通过修改元素使得整个数组变成非递减数列
            return False
        # 将当前元素修改为左边和右边中的最小值,以满足非递减的条件
        nums[i] = min(nums[left], nums[right])
    return True
相关文章
|
2月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
3月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
4月前
|
算法
LeetCode第12题目整数转罗马数字
该文章介绍了 LeetCode 第 12 题整数转罗马数字的解法,通过使用 TreeMap 按照整数从大到小排序,先使用大的罗马数字表示整数,再用小的,核心是先表示完大的罗马数字,想通此点该题较简单。
LeetCode第12题目整数转罗马数字
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
4月前
|
算法
LeetCode第13题目罗马数字转整数
该文章介绍了 LeetCode 第 13 题罗马数字转整数的解法,通过从大到小解析罗马数字,根据罗马数字的特点,按照从大到小的顺序匹配罗马数字和整数的关系,从而解决该问题,同时强调要注意观察题目考查的知识点特征。
|
6月前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
36 1
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
5月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
6月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~