首页 > 其他分享 >非递减or非递增数列

非递减or非递增数列

时间:2022-12-15 10:55:23浏览次数:60  
标签:count 数列 nums int 递增 元素 递减

https://zhuanlan.zhihu.com/p/93486020
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。

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

这个问题困扰了一段时间,主要是数组的情况挺多的,总是有考虑不到的情况。后面找到一种算是巧妙的办法,也正好适用与这个题。
思路是在当前元素大于下一个元素的情况下,根据判断前一个和后一个元素的大小,如果前一个小于等于后一个,那么当前元素的值赋值为下一个元素,否则下一个元素的值赋值为当前元素的值。这样的情况下,如果出现两个位置都是递减的情况,那么肯定不满足。也就是根据下面代码中count来判断此种情况。

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

标签:count,数列,nums,int,递增,元素,递减
From: https://www.cnblogs.com/Szang/p/16984479.html

相关文章

  • 学会CAD文字递增标注、批量查找替换,就能事半功倍!
    CAD制图时,经常会遇到需要使用CAD文字、标注等命令完善图纸参数信息内容的情况。尤其是在标注连续性数字信息、或者批量修改相同文字内容时,传统做法是使用文字命令+复制命令......
  • 洛谷 P1020 导弹拦截(递增子串 DP )
    题目大意:有一个数列,我们要获取一组子串,这个子串必须单调不增。问:(1)最长我们可以获取多长的这种子串(2)这个数列中最多有多少种这种子串解题思路:其中问题一是很典型的DP问题,最......
  • 洛谷 P1233 木棍加工(贪心,递增子串DP)
    题目大意:有矩形A1,A2......An.每个矩形有长宽w,h。现在已知cost:(1)若矩形a的w,h小于矩形b的w,h,那么没有cost(2)其它情况cost+1.现在已知矩形A1,A2...,问怎么得到最少cost.解题思......
  • 1827. 最少操作使数组递增
    1827.最少操作使数组递增classSolution{publicintminOperations(int[]nums){intn=nums.length;intres=0;for(inti=1;i......
  • 1827. 最少操作使数组递增 ----- 贪心算法
    给你一个整数数组 nums (下标从0开始)。每一次操作中,你可以选择数组中一个元素,并将它增加 1 。比方说,如果 nums=[1,2,3] ,你可以选择增加 nums[1] 得到 nums=......
  • 力扣每日一题2022.12.11---1827. 最少操作使数组递增
    给你一个整数数组 nums (下标从0开始)。每一次操作中,你可以选择数组中一个元素,并将它增加 1 。   比方说,如果 nums=[1,2,3] ,你可以选择增加 nums[1] 得到 n......
  • 斐波那契数列
    intnextTerm(intn){ inta=0,b=1,c,e; if(n==2) { returnb; } elseif(n==1) { returna; } else { for(e=3;e<=n;e++) { c=a+b; a=b; ......
  • 斐波那契数列
    输入一个整数 n ,求斐波那契数列的第 n 项。假定从 0 开始,第 0 项为 0。classSolution{public:intFibonacci(intn){if(n<2)returnn;......
  • 斐波那契数列
    我们都知道斐波那契数(也叫兔子数)是一组十分有趣的数字,首相为1,第二项也是1,之后的每一项就是前两项之和,那么该如何实现输入第n项就打印其对应的斐波那契数字呢?递归实现事实上,......
  • 数列知识总结梳理
    本篇文章重点梳理数列章节相关的知识,以及在求解数列相关问题时比较常用且能较好地简便计算的方法。有关等差数列与等比数列的内容本文主要是以给出性质为主,中点在于后两部......