力扣-贪心算法4
406.根据身高重建队列
406. 根据身高重建队列
题目
假设有打乱顺序的一群人站成一个队列，数组
people表示队列中一些人的属性（不一定按顺序）。每个people[i] = [hi, ki]表示第i个人的身高为hi，前面 正好 有ki个身高大于或等于hi的人。请你重新构造并返回输入数组
people所表示的队列。返回的队列应该格式化为数组queue，其中queue[j] = [hj, kj]是队列中第j个人的属性（queue[0]是排在队列前面的人）。示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]提示：
1 <= people.length <= 20000 <=<=
0 <=< people.length
- 题目数据确保队列可以被重建
题解
这个题的要求是前面 正好 有
ki个身高大于或等于hi的人。举例子，对于第i个人，身高hi，前面有ki个比他高。这里要注意一个点，前面ki个比他高，也可能有比他矮的。那么我们可以从高到矮来排列。如果身高一致，那就按照ki从小到大来排列。
sort(people.begin(),people.end(),[](vector<int>& a,vector<int>& b){return a[0]>b[0] || (a[0]==b[0]&&a[1]<b[1]); });对于第i个人，就插入到第ki个位置。（关键点还是在于，后面插入的人，也就是矮个子的人插入到前面对前面是无影响）
代码如下
class Solution { public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(),people.end(),[](vector<int>& a,vector<int>& b){return a[0]>b[0] || (a[0]==b[0]&&a[1]<b[1]);});vector<vector<int>> ans;for(vector<int>& p:people){ans.insert(ans.begin()+p[1],p);}return ans;} };
665.非递减数列
665. 非递减数列
题目
给你一个长度为
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.length1 <= n <=-105 <= nums[i] <=
题解
找对所谓的对比点。nums[i] <= nums[i + 1]。对于第i个点，实际上的对比点应该是i-2。
第一种情况是nums[i]>nums[i-2].如果第i个点是5，前面是47.也就是475.
这个时候把nums[i-1]变成nums[i-2]~nums[i]之间就可以。
也就是把7变成[4,5].
第二种情况是nums[i]<nums[i-2].如果第i个点是3，前面是47，也就是473.
但是这个时候不知道i+1是怎么样的。所以保险就是让nums[i]=nums[i-1].
第一种情况中需要改变的点本身就在一个非递减数列内，不会破坏后面非递减数列的连续性，不会破坏后面非递减数列的连续性，不会破坏后面非递减数列的连续性，那么我们只需要记录有这么一个点，不对它做处理就可以。
第二种情况中需要改变的点在2个非递减数列的中间，会破坏前后非递减数列的连续性，会破坏前后非递减数列的连续性，会破坏前后非递减数列的连续性，那么我们需要记录该点的同时，来改变该点，来达到前后非递减数列的连续性。
class Solution {
public:bool checkPossibility(vector<int>& nums) {int n=nums.size();int i;int count=0;for(i=1;i<n&&count<2;i++){if(nums[i-1]>nums[i]&&++count<2&&i-2>=0&&nums[i-2]>nums[i])nums[i]=nums[i-1];}return count<=1;}
};