美文网首页
LeetCode-非递减数队列

LeetCode-非递减数队列

作者: G_dalx | 来源:发表于2018-09-19 15:35 被阅读0次

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

我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。

示例 1:

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

示例 2:

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

说明: n 的范围为 [1, 10,000]。

思路:
思考什么样的情况下改变一个数据能让一个数组为非递减数队列
第一种情况:乱序元素前后都是有序的,只有它一个乱序
第二种情况:乱序元素在队列的开头或结尾,其他数据也是有序的

代码:

class Solution {
    public boolean checkPossibility(int[] nums) {
        int i = 0,j = nums.length - 1;
        while(i < j && nums[i] <= nums[i + 1])
            i++;
        while(i < j && nums[j] >= nums[j - 1])
            j--;
        System.out.println(i + "----" + j); //找出乱序元素的位置
        int head = 0;
        if(i == 0)
            head = Integer.MIN_VALUE;//为零则乱序元素在开头位置
        else
            head = nums[i - 1];
        int next = (j==nums.length - 1)?Integer.MAX_VALUE:nums[j + 1];//最大为结尾位置
        if(j - i <= 1 && (head <= nums[j] || nums[i] <= next))//判断乱序元素是否只为一个,并是否有序
            return true;
        else
            return false;
    }
}

相关文章

  • LeetCode-非递减数队列

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

  • 并发编程之并发队列

    常见的并发队列有2种:阻塞队列和非阻塞队列。阻塞队列使用锁实现,非阻塞队列使用CAS非阻塞算法实现。这2种队列都是...

  • 2019-03-30

    ##非递##

  • 一道四年级期末试卷题的解题思路和方法。

    在一道减法算式中,被减数、减数、差的和是580,其中减数比差多50,被减数、减数、差各是多少? 思路:利用被减数一...

  • java队列

    非阻塞队列 ConcurrentLinkedQueue ConcurrentLinkedQueue非阻塞无界队列C...

  • 线程池

    [TOC] 线程池 1. 并发队列:阻塞队列和非阻塞队列 区别如下: 入队: 非阻塞队列:当队列中满了的时候,放入...

  • 数组算法相关题目--Swift

    1、提莫攻击 2、 非递减数组 3、最长且连续的的递增序列

  • 并发队列-无界非阻塞队列ConcurrentLinkedQueu

    一、 前言 常用的并发队列有阻塞队列和非阻塞队列,前者使用锁实现,后者则使用CAS非阻塞算法实现,使用非阻塞队列一...

  • NSOperationQueue

    NSOperationQueue NSOperationQueue 队列 包含了 主队列 和 非主队列 ...

  • 665. 非递减数列

    内容 给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。...

网友评论

      本文标题:LeetCode-非递减数队列

      本文链接:https://www.haomeiwen.com/subject/abyinftx.html