665. 非递减数列

难度简单434

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

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

解法

转为求非连续的递增子序列问题

方法一 动态规划

/*
1300ms 6.5MB
*/
func checkPossibility1(nums []int) bool {

	if len(nums) <= 2 {
		return true
	}

	//计算最长的递增子序列长度
	dp := make([]int, len(nums)) //以当前元素为结尾的自增序列长度
	dp[0] = 1
	for i := 1; i < len(nums); i++ {
		tmp := 1
		for j := 0; j < i; j++ {
			if nums[i] >= nums[j] && dp[j]+1 > tmp {
				tmp = dp[j] + 1
			}
		}
		dp[i] = tmp
	}

	cnt := 1
	for i := range dp {
		if dp[i] > cnt {
			cnt = dp[i]
		}
	}
	return cnt >= (len(nums) - 1)
}

方法二 二分加贪心

/*
 二分 贪心法 转为求最长非连续递增子序列问题 44ms 6.7MB
[1,2,4]  new 3 ,fount 3, get  [1,2,3]  //单调递增
[1,2,4]  new 3 ,found 4, get  [1,2,3]  //递增

[1,2,4]  new 2, found 2, get  [1,2,4]  //单调自增
[1,2,4]  new 2, found 3, get  [1,2,2]  //递增
*/
func checkPossibility(nums []int) bool {

	if len(nums) <= 2 {
		return true
	}

	//计算最长的递增子序列长度
	increNums := []int{nums[0]} //维护当前可以构建的递增序列
	for i := 1; i < len(nums); i++ {

		//因为是可以有重复，所以这里查询的时候要+1
		pos := sort.SearchInts(increNums, nums[i]+1)
		if pos == len(increNums) {
			increNums = append(increNums, nums[i])
		} else {
			increNums[pos] = nums[i]
		}

	}

	return len(increNums) >= (len(nums) - 1)

}

Rust

/*
 * @Description: 665
 * @Version: 2.0
 * @Author: kingeasternsun
 * @Date: 2021-02-07 10:08:19
 * @LastEditors: kingeasternsun
 * @LastEditTime: 2021-02-07 11:19:14
 * @FilePath: \665checkPossibility\check_possibility\src\lib.rs
 */
pub struct Solution;

impl Solution {
    pub fn check_possibility(nums: Vec<i32>) -> bool {
        let mut incre_nums = Vec::new();
        let nums_len = nums.len();
        for n in nums {
            // println!("{:?}",incre_nums);
            let idx = incre_nums.binary_search(&(n+1)).unwrap_or_else(|x| x);
            if idx == incre_nums.len(){
                incre_nums.push(n);
            }else{
                //如果找到了 要在处理下 找到最左边界
                let mut j = idx;
                loop{
                    if j ==0 {
                        break;
                    }

                    if incre_nums[j-1]!=incre_nums[j]{
                        break;
                    }
                    j-=1;
                }
                
                incre_nums[j]=n;
            }

            // println!("after {:?}",incre_nums);


        }

        return incre_nums.len() >=nums_len-1
    }
}
//4 ,5, 1,2,3

#[cfg(test)]
mod tests {
    use crate::Solution;

    #[test]
    fn it_works() {
        assert_eq!(Solution::check_possibility(vec![4,2,3]),true);
        assert_eq!(Solution::check_possibility(vec![4,2,1]),false);
        assert_eq!(Solution::check_possibility(vec![2,3,3,2,2]),false);
    }
}