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;}
};
