题目总结-最长上升子序列问题

LeetCode系列 10 分钟 读完 (约 1432 字)

由最长上升子序列问题引出的一系列力扣相关问题合集。

0x01. 300 最长递增子序列

1. 通用解法

以动态规划的方法去考虑该问题，令 dp[i] 为以 i 下标结尾的 [0, i] 个数组元素的最长递增子序列的长度，其 dp 初始化的每个值为 1 ，要上升就要和之前的每个元素去比较，如何比之前的 j 位置的元素大，在其基础上 + 1 ，最终选取一个最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
            	// 与 i 之前的每一个 j 位置进行比较，大于则总长度 +1;
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

2. 贪心解法

贪心解法不是本文的重点，因此只列出代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<int> dp;
        for (int i = 0; i < n; ++i) {
            if (dp.empty() || dp.back() < nums[i]) dp.push_back(nums[i]);
            else {
                auto iter = lower_bound(dp.begin(), dp.end(), nums[i]);
                *iter = nums[i];
            }
        }
        return dp.size();
    }
};

0x02. 435 无重叠区间

1. 通用解法

本题我们也可以看作最长上升子序列，由于是二维数据，我们首先需要对所有区间元素按照第一维度进行升序排列，只要后续区间 i 的第二维的值 >= 前面 j 位置的第一维的值，即可发生上升转移。(但这样做目前在力扣会超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals[i][0] >= intervals[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        // 按照题意本题只需要最终的dp[n-1]
        return n - dp[n-1];
    }
};

贪心解法

要使剩余区间的个数最多，那么考虑最开始的第一个区间，我们应让其的右边界尽可能的小，因此对所有区间元素按照右边界升序排列（左边界不需要考虑）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 时间复杂度：O(nlogn)
// 空间复杂度：O(logn) 排序需要使用栈空间
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b) {
            return a[1] < b[1];
        });
        int r = intervals[0][1];
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= r) {
                r = max(r, intervals[i][1]);
            }
            else ++ans;
        }
        return ans;
    }
};

0x03. 646 最长数对链

与 0x02 一模一样，就不贴代码了（只是从 >= 变成了严格大于）

0x04. 452 用最少数量的箭引爆气球

通用做法超时了，这里只贴上贪心解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 时间复杂度：O(nlogn)
// 空间复杂度：O(logn) 排序需要使用栈空间
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        int ans = 1;
        int n = points.size();
        sort(points.begin(), points.end(), [](const auto &a, const auto &b) {
            return a[1] < b[1];
        });
        int r = points[0][1];
        for (int i = 1; i < n; ++i) {
            if (points[i][0] > r) {
                ++ans;
                r = max(r, points[i][1]);
            }
        }
        return ans;
    }
};

0x05 354 俄罗斯套娃信封问题

又是一个二维的上升子序列问题…只不过这道题要求必须严格大于，因此我们在对第一维度的的升序排列的基础上，让第二维降序排列，这样做之后我们在后续遍历比较时对于第一维度相等的两个元素直接可以跳过。但这样做会超时…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) return 0;
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto &a, const auto &b) {
            return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
        });

        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

于是我们可以对其进行二分优化，就想0x01一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) return 0;
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto &a, const auto &b) {
            return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
        });
        vector<int> d;
        for (int i = 0; i < n; ++i) {
            if (d.empty() || envelopes[i][1] > d.back()) {
                d.push_back(envelopes[i][1]);
            }
            else {
                auto iter = lower_bound(d.begin(), d.end(), envelopes[i][1]);
                *iter = envelopes[i][1];
            }
        }
        return d.size();
    }
};

0x06 面试题 08.13. 堆箱子

与上面一题同样的道理，由于是三维数据，我们对第一维升序排列后，还需要把判断条件写全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        if (box.empty()) return 0;
        int n = box.size();
        sort(box.begin(), box.end());
        vector<int> dp(n, -1);
        for (int i = 0; i < n; ++i) {
            dp[i] = box[i][2];
            for (int j = 0; j < i; ++j) {
            	// 注意三者必须严格大于
                if (box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2])
                    dp[i] = max(dp[i], dp[j] + box[i][2]);
            }   
        }
        return *max_element(dp.begin(), dp.end());
    }
};

0x07 960 删列造序 III

本题也是最长上升子序列的变种，注意数组中字符串的长度均为n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 时间复杂度：O(n^3)
// 空间复杂度：O(n)
class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        if (strs.empty() || strs[0].empty()) return 0;
        int m = strs.size(), n = strs[0].size();
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                int flag = true;
                for (int k = 0; k < m; ++k) {
                    if (strs[k][j] < strs[k][i]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) dp[j] = max(dp[j], dp[i] + 1);
            }
        }
        return n - *max_element(dp.begin(), dp.end());
    }
};
#Algorithm #贪心
使用ssh连接 [Docker] Ubuntu容器
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×