Leetcode 面试题 17.08. 马戏团人塔（DAY 189）---- 二分查找学习期

阳光穿透心脏的1/2处 2022-09-15 15:43 158阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（大部分看解 - -）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（大部分看解 - -） ##

--------------------

class Solution { 
    public:
        int bestSeqAtIndex(vector<int>& height, vector<int>& weight) { 
            vector<pair<int,int>> hw(height.size());
            for(int i=0;i<height.size();++i)
            { 
                hw[i].first = height[i];
                hw[i].second = weight[i];
            }
    
            sort(hw.begin(),hw.end(),[&](auto& a,auto& b){ return a.first < b.first || a.first == b. first && a.second > b.second;});
            if(hw.empty())  return 0;
            vector<int> v;
            v.emplace_back(hw[0].second);
            for(int i=1;i<hw.size();++i)
            { 
                auto pos = lower_bound(v.begin(),v.end(),hw[i].second) - v.begin();
                if(pos == v.size()) v.emplace_back(hw[i].second);
                else    v[pos] = hw[i].second;
            }
            return v.size();
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/cd856835024d4133a0c0013ba2e3f71a.png