学习内容:

LeeCodeJava

665.非递减数列

他人的思路

  1. 这道题给了我们一个数组，说我们最多有1次修改某个数字的机会，
  2.   问能不能将数组变为非递减数组。题目中给的例子太少，不能覆盖所有情况，我们再来看下面三个例子：
  3.     4，2，3
  4.     -1，4，2，3
  5.     2，3，3，2，4
  6. 我们通过分析上面三个例子可以发现，当我们发现后面的数字小于前面的数字产生冲突后，
  7. [1]有时候需要修改前面较大的数字(比如前两个例子需要修改4)，
  8. [2]有时候却要修改后面较小的那个数字(比如前第三个例子需要修改2)，
  9. 那么有什么内在规律吗？是有的，判断修改那个数字其实跟再前面一个数的大小有关系，
  10. 首先如果再前面的数不存在，比如例子1，4前面没有数字了，我们直接修改前面的数字为当前的数字2即可。
  11. 而当再前面的数字存在，并且小于当前数时，比如例子2，-1小于2，我们还是需要修改前面的数字4为当前数字2；
  12. 如果再前面的数大于当前数，比如例子3，3大于2，我们需要修改当前数2为前面的数3。

我的思路

在滑动窗口的时候直接将数字改变好,以减少逻辑的判断,主体的逻辑思路与上面的思路相同.

我的代码

  1. class Solution {
  2.     public boolean checkPossibility(int[] nums) {
  3.         int left=0;
  4.         int right=1;
  5.         int maxNumber =1;
  6.         for (int i = 0; i < nums.length-1; i++) {
  7.             if(nums[left]>nums[right]){
  8.                 maxNumber--;
  9.                 if(maxNumber<0){
  10.                     return false;
  11.                 }
  12.                 if(left==0||nums[left-1]<=nums[right]){
  13.                     nums[left]=nums[right];
  14.                 }else{
  15.                     nums[right]=nums[left];
  16.                 }
  17.             }
  18.             left++;
  19.             right++;
  20.         }
  21.         return true;
  22.     }
  23. }

代码思路:

将整个问题抽象为两个数对比之后的值整改情况,得出值得变化取决于第一个与第三数的对比情况,进而在不同的情况下,分别对于nums[left]与nums[right]分别取值.

优解代码

  1. class Solution {
  2.     public boolean checkPossibility(int[] nums) {
  3.         //记录更改的次数
  4.         int cnt = 0;
  5.        int length = nums.length;
  6.        for (int i = 1; i<length&&cnt<=1; i++){
  7.            //如果后数小于前数
  8.            if (nums[i] < nums[i-1]){
  9.                //计算变化的次数
  10.                cnt++;
  11.                //
  12.                if(i>=2 && nums[i-2] > nums[i]){
  13.                    nums[i] = nums[i-1];
  14.                    //nums[right]=nums[left]
  15.                }
  16.            }
  17.        }
  18.        return cnt <= 1;
  19.     }
  20. }

心得

他只考虑了一种结果,即如果前前个大于这个,则改变这个的值.或者说,他不考虑和结果没有关系的值改变,减少了计算的次数,这个只考虑了nums[i]的值变化,至于为啥nums[left]=nums[right]不用考虑,因为前一个变化的left在下一个比较中不会被取值取到,而在作为nums[left-1] 取值中,其的值与右值相当,只会让nums[left]减小,而不会让他加大,所以可以不考虑.