最長連續序列（困難）
給定一個未排序的整數陣列，找出最長連續序列的長度，
要求演算法的時間復雜度為 O(n)，
示例:
輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長連續序列是 [1, 2, 3, 4]，它的長度為 4，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-consecutive-sequence
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
思路
用哈希集合（hash_set），簡單粗暴，省去排序，
代碼實作
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_set<int> s(nums.begin(), nums.end());
for (int val : nums) {
if (!s.count(val)) continue;
s.erase(val);
int pre = val - 1, next = val + 1;
while (s.count(pre)) s.erase(pre--);
while (s.count(next)) s.erase(next++);
res = max(res, next - pre - 1);
}
return res;
}
俄羅斯套娃問題
給出一些信封，每個信封用寬度和高度的整數對形式（W,H）表示，
當一個信封A的寬度和高度都比信封B要大的時候，則B就可以放進A里，
試問，給你一堆信封，最多你能套幾個，
思路
這個問題，可以看做一個套娃的問題，
首先，我們從小往大了套（個人習慣），
這時候，我們先確定一個邊，比如說寬先拿來升序排序，
如果遇到一樣寬的，就按高度再降序排序，
來個圖看看：
接下來呢？
接下來那不就是最長遞增子序列的問題了嘛，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/264201.html
標籤：其他