Leetcode 665. 非递减数列 (比较恶心的模拟贪心题)

02/08 11:57
阅读数 62

 

从左向右遍历,遇到拐点时有两种处理方法

 

 

下移移动拐点处的元素,不会影响后面的判断,但是要满足条件。nums[i+1]>nums[i-1]

否则就只能上移后面的元素。注意边界情况,最后的代码

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0, pre = INT_MIN;
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i]>nums[i+1]){
                count++;
            }
            if(count>1) {
                cout<<i<<endl;
                return false;
            }
            if(count==1){
                if(nums[i+1]>=pre){
                    nums[i] = pre;
                }else{
                    nums[i+1] = nums[i];
                }
            }
            pre = nums[i];
        }
        return true;
    }
};

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部