《力扣算法训练提升》图解数组篇-打卡数组统计-【665】非递减数列

数组的基本特性

数组是最简单的数据结构。

数组是用来存储一系列相同类型数据，数据连续存储，一次性分配内存。

数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

囧么肥事今日打卡题目

力扣【665.非递减数列】

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

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

具体描述

解题讨论

低谷填坑示例

对于数组构造峰谷折线图

4 1 6 形成低谷，其中 1 为谷底

两端谷峰分别为 4， 6

填平谷底可选取值范围，两端峰值内闭合区域，为了方便，选取两端峰值作为可选填坑值

选取左端峰值作为填坑值

选取右端峰值作为填坑值

讨论归纳

遍历数组，遇到低谷区域，尝试取两端峰值填平低谷。

从右往左遍历，以a[i] 为开始  a[i]~a[N-1] 范围内的数都是递增序列
a[i] < a[L] ? L--
a[i] >= a[L] ? 更新 a[i] = a[L]-1, L--

从左往右遍历，以a[i] 为结束  a[0]~a[i]   范围内的数都是递增序列
a[i] < a[R] ? R++
a[i] >= a[R] ? 更新 a[i] = a[R]+1, R++

动画模拟

示例一：遍历数组，遇到低谷区域，尝试取两端峰值填平低谷

public boolean checkPossibility(int[] nums) {

    // 4 2 3 4
    // 从右往左遍历，以a[i] 为开始  a[i]~a[N-1] 范围内的数都是递增序列
    // a[i] < a[L] ? L--
    // a[i] >= a[L] ? 更新 a[i] = a[L]-1, L--

    // 从左往右遍历，以a[i] 为结束  a[0]~a[i]   范围内的数都是递增序列
    // a[i] < a[R] ? R++
    // a[i] >= a[R] ? 更新 a[i] = a[R]+1, R++

	// 备份数组
    int[] copy = Arrays.copyOf(nums, nums.length);

    int L = nums.length - 1;
    int R = 0;

    int countR = 0;
    // 从左往右遍历
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[R]) {
            nums[i] = nums[R];
            countR++;
        }
        R++;
    }

    nums = copy;
    int countL = 0;
    // 从右往左遍历
    for (int i = L - 1; i >= 0; i--) {
        if (nums[i] > nums[L]) {
            nums[i] = nums[L];
            countL++;
        }
        L--;
    }

    return countL <= 1 || countR <= 1;
}

复杂度分析

时间复杂度：O(n)。遍历数组，需要O(n)时间。
空间复杂度：O(n)。需要额外空间。

通过示例一可以发现，我们借用了O(n) 的数组存储给定原始数组状态，遍历数组的时候更新修改数组中的值。

实际上，我们不需要真正的去更改数组中元素的值，借用窗口边界，我们只需要更新边界即可！

通过两个临时变量 L, R 作为窗口的边界

遍历数组，更新 L R 边界值

从左遍历 以 R 为界，左边满足非递减数列
从右遍历 以 L 为界，右边满足非递减数列

示例二：空间优化，节省空间，只更新边界值

// 省去 O(n) 空间，只更新边界
public boolean checkPossibility(int[] nums) {

    // 更新 R L 边界
    // 从左遍历 以 R 为界，左边满足非递减数列
    // 从右遍历 以 L 为界，右边满足非递减数列

    int L = nums[nums.length - 1];
    int R = nums[0];

    int countR = 0;
    // 从左往右遍历
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < R) {
            countR++;
            continue;
        }
        R = nums[i];
    }

    int countL = 0;
    // 从右往左遍历
    for (int i = nums.length - 1; i >= 0; i--) {
        if (nums[i] > L) {
            countL++;
            continue;
        }
        L = nums[i];
    }

    return countL <= 1 || countR <= 1;
}

复杂度分析

时间复杂度：O(n)。 遍历数组，需要O(n)时间。
空间复杂度：O(1)。需要常量级额外空间。

实际上，读者可以发现，这里我分别遍历了两次数组，分别是上坡填坑和下坡填坑。

从左往右遍历，保证了一路上去都是上坡或者平坡，遇坑填坑。
上坡遇坑，我们选择低峰值作为填坑数！


从右往左遍历，保证了一路下来都是下坡或者平坡，遇坑填坑。
下坡遇坑，我们选择高峰值作为填坑数！

这里可以再简化为一次遍历

// 7 1 2 3 5
对于首位数较大，或者是 a[i] >= a[i-2] 时，我们选择高峰值置换 a[i-1]
// 本例首位数较大，置换后
// 1 1 2 3 5


否则，使用低峰值置换当前数 a[i] = a[i-1]
// 1 2 3 7 5
// 低峰值置换后
// 1 2 3 3 5

public boolean checkPossibility(int[] nums) {

    int countR = 0;
    // 从左往右遍历
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) {
            // 7 1 2 3 5
            // 1 2 4 7 6
            if (i == 1 || nums[i] >= nums[i - 2]) {
                nums[i - 1] = nums[i];
            } else {
                nums[i] = nums[i - 1];
            }
            countR++;
        }
    }

    return countR <= 1;
}

短话长说

学算法先学什么？什么阶段该刷什么题？

关注我，日常打卡算法图解。

按照力扣题目类别结构化排序刷题，从低阶到高阶，图解算法(更新中…)，有兴趣的童鞋，欢迎一起从小白开始零基础刷力扣，共同进步！

回复：678，获取已分类好的部分刷题顺序，后续内容会持续更新，感兴趣的小伙伴自由拿取！

另外，有关分类，求小伙伴们不要再问我最后一类的起名了，奇技淫巧是个褒义词，意思是指新奇的技艺和作品。

力扣修炼体系题目，题目分类及推荐刷题顺序及题解

目前暂定划分为四个阶段：

算法低阶入门篇--武者锻体

算法中级进阶篇--武皇炼心

算法高阶强化篇--武帝粹魂

算法奇技淫巧篇--战斗秘典

以上分类原谅我有个修仙梦...

缺漏内容，正在努力整理中…

Tags: 《力扣算法图解》力扣算法图解囧么肥事算法图解算法趣说