题目描述:
Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
- We define an array is non-decreasing if
- array[i] <= array[i + 1]
- holds for every i (1 <= i <n).
- Example 1:
- Input: [4,2,3]
- Output: True
- Explanation: You could modify the first
- 4
to 1 to get a non-decreasing array.
- Example 2:
- Input: [4,2,1]
- Output: False
Explanation: You can't get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].
要完成的函数:
bool checkPossibility(vector<int>& nums)
说明:
1, 这道题目给定一个 vector, 要判断这个 vector 至多改变一个元素的值之后, 是不是变成了非减序列.
首先笔者想的是, 比如序列[1,4,2,3], 这个序列改变 4 的值也就可以了, 这样子的序列中间必然会有一个凸起, 4 就是这个凸起.
那我们可以先找到这个凸起, 从前往后找跟从后往前找, 如果只有一个凸起的话, 那么就接着判断, 如果有多个凸起, 那么必定不能只改一个元素.
部分代码如下:
- int s1=nums.size();
- int i=0,j=s1-1;
- while(i<s1-1)
- {
- if(nums[i]<=nums[i+1])
- i++;
- else
- break;
- }
- if(i==j)// 当整个序列非降序排列
- return true;
- while(j>i)
- {
- if(nums[j]>=nums[j-1])
- j--;
- else
- break;
- }
- if((j-1)!=i)// 如果中间有多个元素
- return false;
这样子就记录了 i 和 j 的值.
2, 当确实只有一个凸起时, 我们进行下一步判断.
还是以上面提到的序列为例子,[1,4,2,3],i=1,j=2, 这个凸起的形成是由于 nums[i]>nums[j], 那我们可以改 i 这一位的值, 也可以改 j 这一位的值, 使得 nums[i]<=nums[j].
怎么判断什么时候要改 i 的值, 什么时候要改 j 的值?
比如 [3,4,2,5],i=1,j=2, 这时候由于 nums[i] 的前一位 3, 大于 nums[j]=2, 所以我们只能修改 j 这一位的值, 而不能修改 i 这一位的值.
那如果 nums[i]的值, 还是比 nums[j]的下一位大呢, 这时候我们就算修改 j 这一位的值, 修改完也不能形成非减序列, 这时候就要返回 false.
如果 nums[i]的值, 小于等于 nums[j]的下一位, 那这时候就要返回 true 了.
还有另一种情况, 如果 nums[i]的前一位, 小于等于 nums[j], 比如上面提到的[1,4,2,3],i=1,j=2, 那这时候我们就可以修改 i 的值了, 直接返回 true 即可.
代码如下:
- if(i!=0)
- {
- if(nums[i-1]>nums[j])// 只能改 j 这一位
- {
- if(j==s1-1)
- return true;
- if(nums[i]>nums[j+1])
- return false;
- return true;
- }
- else
- return true;
- }
- return true;// 如果 i==0, 那么直接修改 nums[i]的值就可以了
上述代码虽然考虑的过程繁琐了点, 但是实测 38ms,beats 86.96% of cpp submissions, 效果还是可以的.
3, 附上完整代码, 分享给大家, 如下:
- bool checkPossibility(vector<int>& nums)
- {
- int s1=nums.size();
- int i=0,j=s1-1;
- while(i<s1-1)
- {
- if(nums[i]<=nums[i+1])
- i++;
- else
- break;
- }
- if(i==j)
- return true;
- while(j>i)
- {
- if(nums[j]>=nums[j-1])
- j--;
- else
- break;
- }
- if((j-1)!=i)
- return false;
- if(i!=0)
- {
- if(nums[i-1]>nums[j])// 只能改 j 这一位
- {
- if(j==s1-1)
- return true;
- if(nums[i]>nums[j+1])
- return false;
- return true;
- }
- elsereturn true;
- }
- return true;
- }
- leetcode-665-Non-decreasing Array
来源: http://www.bubuko.com/infodetail-2596368.html