LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 先将数组按宽度升序排列，这样后面的一定比前面宽，只要后面的再比前面高就可以嵌套，此时问题转化为求高度的最长升序子序列长度，使用 #300 的解法即可。因为相同高度不能嵌套，所以排序时，对于相同宽度，把高度高的放前面

[5,4], [6, 4], [6, 7], [2, 3] => [2, 3], [5, 4], [6, 7], [6, 4]
求 3474 的最大升序子序列长度，即 347，长度为 3

• 动态规划，dp[i] 表示以 envelopes[i][1] 结尾的最长子序列长度

class Solution {
 public:
  int maxEnvelopes(vector<vector<int>>& envelopes) {
    if (empty(envelopes)) {
      return 0;
    }
    sort(begin(envelopes), end(envelopes),
         [](auto& x, auto& y) { return tie(x[0], y[1]) < tie(y[0], x[1]); });
    vector<int> dp(size(envelopes), 1);
    int res = 1;
    for (int i = 0; i < size(dp); ++i) {
      for (int j = 0; j < i; ++j) {
        if (envelopes[i][1] > envelopes[j][1]) {
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
      res = max(res, dp[i]);
    }
    return res;
  }
};

• 二分查找优化解法

class Solution {
 public:
  int maxEnvelopes(vector<vector<int>>& envelopes) {
    if (empty(envelopes)) {
      return 0;
    }
    sort(begin(envelopes), end(envelopes),
         [](auto& x, auto& y) { return tie(x[0], y[1]) < tie(y[0], x[1]); });
    vector<int> v{envelopes[0][1]};
    for (int i = 1; i < size(envelopes); ++i) {
      if (envelopes[i][1] > v.back()) {
        v.emplace_back(envelopes[i][1]);
      } else {
        *lower_bound(begin(v), end(v), envelopes[i][1]) = envelopes[i][1];
      }
    }
    return size(v);
  }
};