665. 非递减数列

以你之姓@ 2023-10-05 19:24 44阅读 0赞

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

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

**示例 1:**

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

**示例 2:**

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

**说明：**

*  `1 <= n <= 10 ^ 4`
 *  `- 10 ^ 5 <= nums[i] <= 10 ^ 5`

public class Solution665 {
    	public boolean checkPossibility(int[] nums) {
    
    		int out = -1;
    		int count1 = 0;
    		int count2 = 0;
    
    		int i = 0;
    
    		i = 0;
    		int[] nums1 = nums.clone();
    		while (i < nums1.length - 1) {
    			//System.out.println(nums1[i] + ":count1:" + nums1[i + 1]);
    			if (nums1[i] > nums1[i + 1]) {
    				count1 = count1 + 1;
    				nums1[i] = nums1[i + 1];
    				i = 0;
    
    			} else {
    				i++;
    			}
    
    		}
    		//System.out.println(count1);
    		i = 0;
    		int[] nums2 = nums.clone();
    		while (i < nums2.length - 1) {
    			//System.out.println(nums2[i] + ":count2:" + nums2[i + 1]);
    			if (nums2[i] > nums2[i + 1]) {
    				count2 = count2 + 1;
    				nums2[i + 1] = nums2[i];
    				i = 0;
    
    			} else {
    				i++;
    			}
    
    		}
    		System.out.println(count2);
    		if ((count1 > 1) && (count2 > 1)) {
    			return false;
    		}
    
    		return true;
    	}
    
    	public static void main(String[] args) {
    
    		Solution665 s = new Solution665();
    
    		int[] nums = { 4, 2, 3 };
    
    		for (int n : nums) {
    			System.out.println(n);
    		}
    
    		System.out.println(s.checkPossibility(nums));
    	}
    }

以上代码英文leetcode提交成功，中文力扣超时，只好继续优化

class Solution {
    	public boolean checkPossibility(int[] nums) {
    
    		int count1 = 0;
    		int count2 = 0;
    
    		int i = 0;
    
    		i = 0;
    		int[] nums1 = nums.clone();
    		while ((count1<2)&&(i < nums1.length - 1)) {
    			// System.out.println(nums1[i] + ":count1:" + nums1[i + 1]);
    			if (nums1[i] > nums1[i + 1]) {
    				count1 = count1 + 1;
    				nums1[i] = nums1[i + 1];
    				i = 0;
    
    			} else {
    				i++;
    			}
    
    		}
    		// System.out.println(count1);
    		i = 0;
    		// int[] nums2 = nums.clone();
    		while ((count2<2)&&(i < nums.length - 1)) {
    			// System.out.println(nums2[i] + ":count2:" + nums2[i + 1]);
    			if (nums[i] > nums[i + 1]) {
    				count2 = count2 + 1;
    				nums[i + 1] = nums[i];
    				i = 0;
    
    			} else {
    				i++;
    			}
    
    		}
    		// System.out.println(count2);
    		if ((count1 > 1) && (count2 > 1)) {
    			return false;
    		}
    
    		return true;
    	}
    
    }

这次中文力扣也通过，击败了99.54%的用户

执行结果：

通过

显示详情

执行用时：1 ms, 在所有 Java 提交中击败了99.54%的用户

内存消耗：39.5 MB, 在所有 Java 提交中击败了95.69%的用户