力扣665. 非递减数列 475.供暖屋

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 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 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。 提示：

• n == nums.length
• 1 <= n <= 104
• -105 <= nums[i] <= 105 思路: 当我们遇见nums[i]<=nums[i+1],且nums[i+1]>nums[i+2]时 1.如果nums[i+2]=nums[i+1]才能将序列变为非递减序列 举例:[2,3,1,4]->[2,3,3,4] 2.如果nums[i+2]>=nums[i],那么我们可以选择增加nums[i+2]或者减小nums[i+1],我们要选择减小nums[i+1],这样会让后面的序列更容易变成递增序列,特别注意 i=0时,nums[i] >nums[i+1],选择将nums[i]减小 举例:[2,4,3,5]->[2,3,3,5]| [2,4,4,5] 代码参考: class Solution { public boolean checkPossibility(int[] nums) { int cnt=0; for(int i=0;iy){ if(cnt>0){return false;} cnt++; if(i>0&&y=Math.abs(heaters[j+1]-houses[i])){ j++; //寻找离当前房屋最近的供暖器 curDistance=Math.min(curDistance,Math.abs(houses[i]-heaters[j])); } maxR=Math.max(maxR,curDistance); } return maxR; } }