300. Longest Increasing Subsequence

有時間可以看一下這影片的講解, 很詳細

https://www.youtube.com/watch?v=fV-TF4OvZpk&ab_channel=BackToBackSWE

這題就是要在裡面找出最大遞增的子陣列, 但不用給出陣列, 你只需給出個數就好

我們可以用dp, 怎麼用呢,首先先產生一維的陣列, 產生完之後, 掃過一輪

再掃的同時, 我們往回檢查當前的這個值是否大於前面的數字, 若有

我們只需將前面數字累積的遞增個數再加1就好(一開始都是1) ,

例如
[1, 2, 3]
當i在1時 dp [1, 2, X]
當i 在2時, 我們發現3比1還要高, 所以我們就拿他的數加1
dp [1,2,2]
我們再往下看 發現3也比2還要大, 所以我們就是拿剛剛比到的跟新增的在比較一次 max(nums[i], nums[j] + 1), 當然2 + 1 = 3更大
所以dp更新成
dp[1,2,3]

大概就是這樣, 在每做完一個數, 我們就紀錄當前最大值是多少(並不是最後面那個喔)

舉例

[1,2,3,5,6,1,2]
dp對應為
[1,2,3,4,5,1,2] 最大是5喔

時間複雜度為O(n²)

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        vector<int> dp(nums.size(), 1);
        if (nums.size() == 1) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

但這題是我為了做binary search而來的, 說真的我還看不出這要怎麼二分

首先先建立一個空陣列(B), 放進第一個數

接著我們建立三個判斷

對陣列做一次遍歷
1. 若值比B的最小值還要小, 我們就換掉這個最小值
2. 若值比B的最大值還要大, 我們就加到B的最尾端
3. 以上兩個都沒有, 我們就用二分搜尋法, 找到在陣列中, 最接近且大於值的位置, 做替換

時間複雜度為O(nlogn)

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        vector<int> array{nums[0]};
        for (auto &n : nums) {
            if (n < array[0]) {
                array[0] = n;
            } else if (n > array.back()) {
                array.push_back(n);
            } else {
                int r = array.size() - 1;
                int l = 0;
                while (l <= r) {
                    int mid = (r + l) / 2;
                    if (array[mid] > n) {
                        r = mid - 1;
                    } else if (array[mid] < n) {
                        l = mid + 1;
                    } else {
                        l = mid;
                        r = l - 1;
                    }
                }
                array[l] = n;
            }
        }
        return array.size();
    }
};

更簡潔的話, 我們還可以使用lower_bound

class Solution {
public:
  int lengthOfLIS(vector<int> &nums) {
    vector<int> res;
    for(int i = 0; i < nums.size();i++){
      auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
      if(it == res.end()) res.push_back(nums[i]);
      else{
        *it = nums[i];
      }
    }
    return res.size();
  }
};