406.根据身高重建队列

错误解答

bool f(const vector<int>&a, const vector<int>&b) {
    if (a[1]==b[1])return a[0]>b[0];return a[1]<b[1];
}
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
        vector<vector<int>> res;
        sort(p.begin(),p.end(),f);
        for ( auto peo: p ) {
            if (peo[1]!=0) break;
            res.push_back(peo);
        }
        reverse(res.begin(),res.end());
        for (int i = res.size(); i < p.size(); i ++ ) {
            auto x = p[i];
            int insert_pos = 0; int cnt = 0;
            while ( cnt < x[1] + 1 ) {
                if (p[insert_pos][0] >= x[0]) cnt ++ ;
                insert_pos ++ ;
            }
            res.insert(res.begin()+insert_pos - 1,x);
        }
        return res;
    }
};

这道题我没有能够做出来

在135. 分发糖果 (opens new window)我就强调过一次，遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。

如果两个维度一起考虑一定会顾此失彼。

我就是错误的按照k来从小到大排序了

bool f(vector<int>& a, vector<int>& b){
    if(a[0]==b[0])return a[1]<b[1];return a[0]>b[0];
}
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& p) {
        vector<vector<int>> res;
        sort(p.begin(),p.end(),f);
        for (int i = 0; i < p.size(); i ++ ) {
            auto x = p[i];
            int pos = x[1];
            res.insert(res.begin()+pos,x);
        }
        return res;
    }
};

先按照身高排序，固定住规律。按照k排序没法获得额外的规律