LeetCode算法题-Non-decreasing Array（Java实现）

这是悦乐书的第283次升级，第300篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第151题（顺位题号是665）。给定一个包含n个整数的数组，您的任务是通过修改最多1个元从来检查它能否可以变为非递减。假如array [i] <= array [i + 1]，且0 <= i <n，则我们定义一个数组是非递减的。例如：

输入：[4,2,3]
输出：true
说明：可以修改4为1或者2以取得非递减数组。

输入：[4,2,1]
输出：false
说明：通过最多修改一个元素，无法取得非递减数组。

注意：n的范围在[1,1,000]。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

题目的意思是是否只在一步内，将原数组变成一个非递减的数组，也就是递增的数组，并且元素之间的关系是小于等于，即nums[i] <= nums[i+1]，0 <= i < n。

特殊情况：数组内的元素小于等于两个，直接返回true。

正常情况：什么情况下，需要修改原数组元素的值？当前元素比前一个元素小的时候，这时我们需要进一步判断，是改当前元素还是改前一个元素？是改大还是改小？

假如当前元素小于其前一个元素：

第一种情况，假如当前元素是数组的第二个元素，改当前元素的前一个元素，前一个元素往小改，将当前元素的值赋值给当前元素的前一个元素；

第二种情况，假如当前元素比其前前个元素值要大，前一个元素往小改，将当前元素的值赋值给当前元素的前一个元素；

第三种情况，当第一和第二种情况都不满足的时候，当前元素往大改，将当前元素的前一个元素值赋值给当前元素。

每改一次都要记数，假如在for循环中count大于1，直接返回false，最后也需要判断count能否小于等于1。

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

03 第二种解法

我们也可以不修改原数组的原始值。先使用一个循环，找到当前数组中需要修改的元素的索引值，做个标记，而后判断该标记能否以下几种情况：

第一：标记还是初始值，说明该数组是一个递增数组，不用修改任何元素就能满足题目要求。

第二：标记等于0，即第一个元素需要修改，也就是说数组中只有第一个元素大于第二个元素，从第二个元素开始，数组是递增的，只用修改第一个元素就能是整个数组递增。

第三：标记等于数组倒数第二个索引，也就是说倒数第二个元素大于倒数第一个元素，也只要要改一个元素就可。

第四：标记所在元素的前一个、后一个元素之间的关系是小于等于，而标记所在的元素大于后一个元素，所以也只用该标记所在的元素就可。

第五：标记所在的元素比其下下个元素要小或者者相等，而标记所在元素比下一个元素要大，也只要要改小标记所在元素就可。

假如是上面这五种情况，表示都符合题目的要求，假如不满足，直接返回false。

public boolean checkPossibility2(int[] nums) {    if (nums.length <= 2) {        return true;    }    // 初始化索引值为-1    int index = -1;    for (int i=0; i<nums.length-1; i++) {        // 假如当前元素比后一个元素大，说明遇到了需要修改的元素        if (nums[i] > nums[i+1]) {            // 假如索引值为-1，表示是第一次遇到需要修改的元素，否则表示已经屡次遇到需要修改的值了            if (index == -1) {                // 将其索引赋值给index                index = i;            } else {                return false;            }        }    }    // index为-1表示原数组本身就是个递增数组，为0表示，只用修改第一个元素就可，为nums.length-2表示只用修改倒数第二个元素就可    if (index == -1 || index == 0 || index == nums.length-2) {        return true;    }    // index所在元素的前后元素是小于等于的关系    if (nums[index-1] <= nums[index+1]) {        return true;    }    // index所在元素的小于等于其下下个元素    if (nums[index] <= nums[index+2]) {        return true;    }    return false;}

04小结

算法专题目前已日更超过四个月，算法题文章151+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是一律内容，假如大家有什么好的解法思路、建议或者者其余问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！