LeetCode - LIS Series

LeetCode - LIS Series

LAVI
  2026-05-07 2026-05-07 Created   2026-05-07 2026-05-07 Updated      

Easy Medium Hard

300. Longest Increasing Subsequence 673. Number of Longest Increasing Subsequence 674. Longest Continuous Increasing Subsequence 354. Russian Doll Envelopes 646. Maximum Length of Pair Chain 1048. Longest String Chain

我的另一篇文章有解說各種 LIS & LCS 的解題思路，可以參考看看：

Algorithm - DP LIS and LCS

300. Longest Increasing Subsequence

題目

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 10^4

Follow up

Can you come up with an algorithm that runs in O(n log(n)) time complexity?

解題思路

這題是經典 LIS 題
目標是找最長嚴格遞增子序列的長度

  • 使用 lisdp 紀錄目前每個長度的 LIS 最小結尾值

    • lisdp[i] 代表長度為 i + 1 的 increasing subsequence，目前最小的結尾值

  • 對每個數字 x

    • 使用 lower_bound 找到第一個 >= x 的位置

  • 如果 x 比目前所有結尾值都大

    • 代表可以接在目前 LIS 後面
    • lisdp.push_back(x)

  • 否則：

    • 用 x 取代第一個 >= x 的位置
    • 代表同樣長度下，保留更小的結尾值
    • 之後才更容易接上新的數字

  • 最後答案為：
    lisdp.size()

Solution Code

Time Complexity
O(n log n)

Space Complexity
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> lisdp;

        for(int x: nums){
            auto it = lower_bound(lisdp.begin(), lisdp.end(), x);

            if (it == lisdp.end()) lisdp.push_back(x);
            else *it = x;
        }

        return lisdp.size();
    }
};

673. Number of Longest Increasing Subsequence

題目

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

Constraints

  • 1 <= nums.length <= 2000
  • -10^6 <= nums[i] <= 10^6
  • The answer is guaranteed to fit inside a 32-bit integer.

解題思路

這題是 LIS 的計數版本
不只要找最長長度，還要找有幾個 LIS

  • DP 定義：

    • len[i]：以 nums[i] 結尾的 LIS 長度
    • count[i]：以 nums[i] 結尾，長度為 len[i] 的 LIS 數量

  • 初始化：

    • 每個數字自己都可以形成長度為 1 的 LIS
    • 所以 len[i] = 1
    • count[i] = 1

  • 枚舉每個 i

    • 再枚舉前面的 j
    • 如果 nums[j] < nums[i]
      • 代表 nums[i] 可以接在 nums[j] 後面

  • 如果 len[j] + 1 > len[i]

    • 代表找到更長的 LIS
    • 更新 len[i] = len[j] + 1
    • 數量直接覆蓋成 count[j]

  • 如果 len[j] + 1 == len[i]

    • 代表找到另一批同樣長度的 LIS
    • 數量累加：
      count[i] += count[j]

  • 最後找出所有 len[i] == maxLen 的位置

    • 把對應的 count[i] 加總

Solution Code

Time Complexity
O(n^2)

Space Complexity
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1);
        vector<int> count(n, 1);

        int maxLen = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j]; // 更長就覆蓋數量
                    }
                    else if(len[j] + 1 == len[i]) count[i] += count[j]; // 一樣長就累加數量 (加上另一批同樣長度的LIS)
                }
            }
            maxLen = max(maxLen, len[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (len[i] == maxLen)  ans += count[i];
        }
        return ans;
    }
};

674. Longest Continuous Increasing Subsequence

題目

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence, i.e. subarray. The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example 1

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

Example 2

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly increasing.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9

解題思路

這題是 LCIS
也就是 Longest Continuous Increasing Subsequence

和 LIS 最大差別是：

  • LIS 不要求連續

  • LCIS 要求連續

  • DP 定義：

    • dp[i]：以 nums[i] 結尾的最長連續遞增子序列長度

  • 初始化：

    • 每個數字自己都可以形成長度為 1 的連續遞增子序列
    • 所以 dp[i] = 1

  • 狀態轉移：

    • 如果 nums[i-1] < nums[i]
      • 代表 nums[i] 可以接在 nums[i-1] 後面
      • dp[i] = dp[i-1] + 1

  • 如果 nums[i-1] >= nums[i]

    • 代表連續遞增中斷
    • dp[i] 維持 1

  • 最後答案為：
    所有 dp[i] 的最大值

Solution Code

Time Complexity
O(n)

Space Complexity
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);

        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i-1] < nums[i]) {
                dp[i] = max(dp[i], dp[i-1] + 1);
            }

            ans = max(ans, dp[i]);
        }

        return ans;
    }
};

354. Russian Doll Envelopes

題目

You are given a 2D array of integers envelopes where envelopes[i] = [w_i, h_i] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll, i.e. put one inside the other.

Note: You cannot rotate an envelope.

Example 1

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints

  • 1 <= envelopes.length <= 10^5
  • envelopes[i].length == 2
  • 1 <= w_i, h_i <= 10^5

解題思路

這題可以轉成 LIS
因為 envelope 要能套進另一個 envelope，必須同時滿足：

  • width 變大
  • height 也變大

所以可以先排序，再對 height 做 LIS

  • 排序規則：

    • width 由小到大排序
    • 如果 width 一樣，height 由大到小排序

  • 為什麼 width 一樣時，height 要由大到小？

    • 因為 width 一樣的 envelope 不能互相套
    • 如果 height 也由小到大排，後面做 LIS 時可能會錯誤把同 width 的 envelope 接起來
    • 所以 width 相同時 height 由大到小，可以避免被 LIS 選到

  • 排序後：

    • width 已經確保由小到大
    • 接著只需要對 height 做 LIS

  • 使用 dp 紀錄目前每個長度的 LIS 最小結尾高度

    • 對每個 envelope 的 height h
    • 使用 lower_bound 找到第一個 >= h 的位置
    • 如果找不到就 push
    • 否則用 h 取代

  • 最後答案為：
    dp.size()

Solution Code

Time Complexity
O(n log n)

Space Complexity
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        vector<int> dp;

        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0];
        });

        for (int i = 0; i < n; ++i) {
            int h = envelopes[i][1];

            auto it = lower_bound(dp.begin(), dp.end(), h);
            if (it == dp.end()) { // 因為 w 已經被 sort 由小到大排序好了，所以這裡只要抓 h 就好
                dp.push_back(h);
            }
            else *it = h;
        }

        return dp.size();
    }
};

646. Maximum Length of Pair Chain

題目

You are given an array of n pairs pairs where pairs[i] = [left_i, right_i] and left_i < right_i.

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.

Return the length longest chain which can be formed.

You do not need to use up all the given intervals. You can select pairs in any order.

Example 1

Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].

Example 2

Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].

Constraints

  • n == pairs.length
  • 1 <= n <= 1000
  • -1000 <= left_i < right_i <= 1000

解題思路

這題可以用 LIS 的概念來做
目標是找出最長 pair chain

  • pair [a, b] 可以接到 [c, d] 前面，條件是：

    • b < c

  • 先排序：

    • left 由小到大
    • 如果 left 一樣，right 由大到小

  • 使用 listdp

    • listdp[i] 代表長度為 i + 1 的 chain，目前最小的結尾 tail

  • 對每個 pair：

    • head = x[0]
    • tail = x[1]

  • 使用 lower_bound(listdp.begin(), listdp.end(), head)

    • 找到第一個 >= head 的位置
    • 代表目前 pair 可以接在哪個長度後面

  • 如果找不到：

    • 代表可以形成更長的 chain
    • listdp.push_back(tail)

  • 否則：

    • 更新成較小的 tail
    • *it = min(*it, tail)
    • 同長度 chain 保留較小結尾，之後才更容易接新的 pair

  • 最後答案為：
    listdp.size()

Solution Code

Time Complexity
O(n log n)

Space Complexity
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0];
        });

        vector<int> listdp;
        for(auto x: pairs){
            int head = x[0];
            int tail = x[1];

            auto it = lower_bound(listdp.begin(), listdp.end(), head);
            if (it == listdp.end()) listdp.push_back(tail);
            else *it = min(*it, tail); // 同長度 chain 保留較小結尾，之後才更容易接新的 pair
        }
        return listdp.size();
    }
};

1048. Longest String Chain

題目

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example 1

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Example 2

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3

Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • words[i] only consists of lowercase English letters.

解題思路

這題是字串版本的 LIS
每個 word chain 都需要前一個字串是下一個字串的 predecessor

  • predecessor 條件：

    • small.size() + 1 == large.size()
    • large 可以比 small 多一個字元
    • 並且不能改變 small 原本字元的順序

  • 先按照字串長度排序

    • 因為短字串才可能接到長字串前面

  • DP 定義：

    • dp[i]：以 words[i] 結尾的最長 word chain 長度

  • 初始化：

    • 每個 word 自己都可以形成長度為 1 的 word chain
    • 所以 dp[i] = 1

  • 對每個 i

    • 枚舉前面的 j
    • 如果 words[j] 是 words[i] 的 predecessor
      • 代表 words[j] 可以接到 words[i] 前面
      • dp[i] = max(dp[i], dp[j] + 1)

  • 判斷 predecessor：

    • 使用雙指針 i 和 j
    • 如果兩個字元一樣，兩邊都往後走
    • 如果字元不一樣，代表可能是 large 多出來的那個字元
    • 這時只移動 large 的指針
    • 如果 mismatch 超過一次，就不是 predecessor

  • 最後答案為：
    所有 dp[i] 的最大值

Solution Code

Time Complexity
O(n^2 × L)

Space Complexity
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    bool isPredecessor(const string& small, const string& large) {
        if (small.size() + 1 != large.size()) return false; // 每個 LIS 只能比前一個多一字元

        int i = 0, j = 0;
        int mismatch = 0;

        while (i < small.size() && j < large.size()) {
            if (small[i] == large[j]) { // 如果兩個字元一樣，代表這個位置可以對上
                i++;
                j++;
            } else { // 如果字元不一樣，代表可能是 large 多出來的那個字元
                mismatch++;

                // 注意這裡只移動 j，因為假設large[j] 是多出來的字元，把它跳過
                // small[i] 還要繼續跟 large 的下一個字元比較
                j++;

                if (mismatch > 1) return false; // 因為 large 只能比 small 多一個字元，多兩個以上都不行
            }
        }

        return true;
    }

    int longestStrChain(vector<string>& words) {
        int n = words.size();
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() < b.size();
        });

        vector<int> dp(n, 1);
        int ans = 1;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (isPredecessor(words[j], words[i])) { // 如果 words[j] 可以接到 words[i] 前面
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }

            ans = max(ans, dp[i]);
        }

        return ans;
    }
};

Conclusion

這幾題都和 LIS 思想有關，但限制條件不同

  • 300 Longest Increasing Subsequence

    • 最經典 LIS
    • 用 lower_bound 維護每個長度的最小結尾值
    • 時間複雜度可以做到 O(n log n)

  • 673 Number of Longest Increasing Subsequence

    • LIS 計數版本
    • 需要同時維護長度 len
    • 以及每個長度對應的方法數 count

  • 674 Longest Continuous Increasing Subsequence

    • LCIS
    • 要求連續
    • 只需要看前一個元素能不能接上來

  • 354 Russian Doll Envelopes

    • 二維 LIS
    • 先排序 width
    • 再對 height 做 LIS
    • width 相同時 height 要由大到小排序，避免錯誤接在一起

  • 646 Maximum Length of Pair Chain

    • pair chain 版本的 LIS
    • 同長度 chain 保留較小結尾，之後才更容易接新的 pair

  • 1048 Longest String Chain

    • 字串版本的 LIS
    • 先按照長度排序
    • 再判斷前一個字串能不能成為後一個字串的 predecessor

LIS 題型的核心通常是：
找到一種「可以接在前面」的關係，然後維護最長長度

如果只求長度，常常可以用 lower_bound 優化到 O(n log n)
如果還要計數或判斷複雜條件，通常會回到 O(n^2) 的 DP 寫法

On this page
LeetCode - LIS Series
  1. 300. Longest Increasing Subsequence
  2. 題目
  3. 解題思路
  4. Solution Code
  5. 673. Number of Longest Increasing Subsequence
  6. 題目
  7. 解題思路
  8. Solution Code
  9. 674. Longest Continuous Increasing Subsequence
  10. 題目
  11. 解題思路
  12. Solution Code
  13. 354. Russian Doll Envelopes
  14. 題目
  15. 解題思路
  16. Solution Code
  17. 646. Maximum Length of Pair Chain
  18. 題目
  19. 解題思路
  20. Solution Code
  21. 1048. Longest String Chain
  22. 題目
  23. 解題思路
  24. Solution Code
  25. Conclusion