力扣-贪心算法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 <= 2000
• 0 <= <=
• 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.length
• 1 <= 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;}
};