Fork me on GitHub

面试题17.08.马戏团人塔

发表于 | 分类于 ， | 次阅读
字数统计: 405 | 阅读时长 ≈ 1

基本思路

问题要的是一个序列，序列中每个元素中有两个数，前一个元素的第一个和第二个数都比后一个元素的两者大。

我们可以这样，先把元素按第一个数降序排列，然后如果有相同的数，那么按第二个数升序排列，然后按第二个数来求最大下降子序列的长度。

为什么第一个数相同时，按第二个数升序排列？

这是因为如果按第二个数降序排列，而求的是最大下降子序列的长度，那么有可能会产生有两个元素第一个数相同，但是都被选中的结果。而升序排列就避免了这种情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    struct peo{
        int h , w;
    };
    static bool cmp(peo a , peo b){  // 排序
        if(a.h != b.h) return a.h > b.h;
        else return a.w < b.w;
    }
    int bestSeqAtIndex(vector<int>& height, vector<int>& weight) {
        vector<peo> v(height.size());
        for(int i = 0 ; i<height.size() ; ++i){
            v[i].h = height[i];
            v[i].w = weight[i];
        }
        sort(v.begin() , v.end() , cmp);
        vector<int> d(v.size() + 1 , 0);
        d[1] = v[0].w;
        int len = 1;
        for(int i = 1 ; i<v.size() ; ++i){ // 求最大下降子序列的长度
            if(d[len] > v[i].w) d[++len] = v[i].w;
            else {
                int left = 1 , right = len;
                while(left <= right){
                    int mid = (left + right) / 2;
                    if(d[mid] < v[i].w){
                        right = mid - 1;
                    }
                    else left = mid + 1;
                }
                if(d[left - 1] != v[i].w){
                    d[left] = v[i].w;      //d[left]是序列中小于target的最大数
                }
            }
        }
        return len;
    }
};