354. Russian Doll Envelopes

起初我看到, 一度覺得很難

但是看到有人說這是LIS的延伸題, 就特別再去把LIS給複習了一遍

不得不說看教學還是不錯的, 比起文字有時候教學會更powerful一點

看完LIS後, 就自然做得出這題了

用dp的方式

class Solution {
public:
  static bool compare(vector<int> &a, vector<int> &b){
    return a[0] < b[0];
  }
  int maxEnvelopes(vector<vector<int>> &en) {
    sort(en.begin(), en.end(), compare);
    int res = 1;
    vector<int> dp (en.size(), 1);
    for (int j = 1; j < en.size(); j++) {
      for(int i = 0; i < j; i++){
        if (en[i][0] < en[j][0] && en[i][1] < en[j][1]){
          dp[j] = max(dp[j], dp[i] + 1);
        }
        res = max(res, dp[j]);
      }
    }
    return res;
  }
};

但上面的時間複雜度是O(n²), 以LIS的題目來說我們可以優化到O(nlogn)

要怎麼做呢, 我們要怎麼map這個題目到LIS

我們可以先以第一個值做做排序 由小到大, 假設第一個值相等, 會看第二個值, 由大到小

為什麼第二個值要區分開來, 我看了很久都沒有看到說明

原因是做一個區別, 舉一個例子

好如果我們統一看第二個值的排列會變成

[2,4,4,7], 在這邊我們無法判定這兩個四的寬度誰大誰小, 變成你還要再多判斷, 沒辦法用LIS去選取這兩個四,

但如果我們對第二個值做區別

[2,3], [5,4], [6,7], [6,4]

[2,4,7,4], 很明顯, 後方的那個4肯定比7還要小, 這樣我們就可以完全不需要考慮寬度的限制, 這方法太天才了

class Solution {
public:
  static bool compare(vector<int> &a, vector<int> &b) {
    if (a[0] == b[0])
      return a[1] > b[1];
    return a[0] < b[0];
  }
  int maxEnvelopes(vector<vector<int>> &en) {
    sort(en.begin(), en.end(), compare);
    vector<int> res;
for (auto e : en) {
      auto it = lower_bound(res.begin(), res.end(), e[1]);
      if (it == res.end()) {
        res.push_back(e[1]);
      } else {
        *it = e[1];
      }
    }
    return res.size();
  }
};