Leetcode刷题笔记题解（C++）：小红书. 倒卖战利品

讲一下思路吧，

把宝物作为一个结构体，含有x和h属性，将结构体数组依x按从小到大进行排序，如果x相等，则y小的靠前 一点，然后完成了排序。

接着在y排序中寻找最长递增的序列长度。（题目意思可能是没有两个x，h都相等的宝物，如果有还要多考虑一下）

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int max_length(vector<int> &vec);
struct baowu{int x;int h;
};
//结构体数组排序的依据
bool sortall(baowu &b1,baowu &b2){if(b1.x==b2.x) return b1.h<b2.h;else return b1.x<b2.x;
}
int main(){int n;cin>>n;//存放结构体数组vector<baowu>temp(n);for(int i=0;i<n;i++){cin>>temp[i].x>>temp[i].h;}//对结构体数组进行排序sort(temp.begin(), temp.end(),sortall);//单独拿出来排序之后的y属性vector<int>li(n);for(int i=0;i<n;i++){li[i]=temp[i].h;}//求最长递增序列的长度cout<<max_length(li)<<endl;
}//求最长递增序列的长度
int max_length(vector<int> &vec){int length=vec.size();if(length<=1){return length;}vector<int>temp(length);temp[0]=vec[0];int end=0;for(int i=1;i<length;i++){if(vec[i]>temp[end]){end++;temp[end]=vec[i];}else{int left=0,right=end;while(left<right){int mid = left + ((right - left) >> 1);if (temp[mid] < vec[i]) {left = mid + 1;} else {right = mid;}}temp[left]=vec[i];}}end++;return end;
}