题目分析

这个题目作为困难题，一点都不为过，难度确实很大，考察的知识点也很多，也都是非常非常重要的内容，明白了思路，小伙伴们会发现这个题是许多题目的融合，每一道题至少都是中等难度的。

排序

我们恰巧在讲解1673题的时候，讲到过求数组长度为k的最小子序列的求法。当时那个题目使用栈来求解，是一个中等难度的题目。而这个问题是求长度为k的最大子序列，但是要从两个数组中选取。

两个数组选长度为k的子序列，有多少种不同的选法呢？当两个数组长度都大于等于k时，有k+1种选法。nums1选取n个，nums2选取k - n个。其中一个子函数是求解一个数组长度为k的最大子序列，在代码中对应getMaxSubsequence函数。

求出nums1的长度为n的子序列，nums2长度为k - n的子序列后，要对两个子序列进行合并，其中用到了双指针的知识，类似于归并排序。在代码中对应merge函数。

在归并排序的时候，如果从大到小排序，哪一个大则将哪一个值加入结果中，并且索引+1，这个题目也是一样，但是在相等的时候较为复杂。归并排序时，因为子序列一定是有序的，在合并的时候相等时先加入哪一个都是可以的。但是这里子序列并不是按照从大到小排列的，因为要满足长度条件，因此顺序是不能保证的。在两个值相等时要递归比较下一个值是否相等。在代码中对应compare函数。

等到k + 1个序列都比较完成后，最大的用res保存即可。

算法一共要比较k次，在每一次都需要计算两个最大子序列，时间复杂度为$O(m + n)$，两个子序列合并时，如果每一次比较都相等，最坏时间复杂度为$k^2$，因此算法的**时间复杂度为$O(k(m + n + k^2))$，空间复杂度为$O(k)$**。

#include<iostream>
#include<vector>
#include<algorithm>

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res(k, 0);
        for (int i = 0; i <= k; i++) {
            if (nums1.size() >= i && nums2.size() >= k - i) {
                vector<int> subsequence1 = getMaxSubsequence(nums1, i), subsequence2 = getMaxSubsequence(nums2, k - i);
                vector<int> mergeSubsequence = merge(subsequence1, subsequence2);
                if (compare(mergeSubsequence, 0, res, 0)) res = mergeSubsequence;
            }
        }
        return res;
    }

    vector<int> getMaxSubsequence(vector<int>& nums, int k) {
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            while (!res.empty() && res.back() < nums[i] && int(nums.size() + res.size() - k - i - 1) >= 0) res.pop_back();
            if (res.size() < k) res.push_back(nums[i]);
        }
        return res;
    }

    vector<int> merge(vector<int>& nums1, vector<int> nums2) {
        int idx1 = 0, idx2 = 0;
        vector<int> res(nums1.size() + nums2.size());
        for (int i = 0; i < res.size(); i++) res[i] = compare(nums1, idx1, nums2, idx2) ? nums1[idx1++] : nums2[idx2++];
        return res;
    }

    bool compare(vector<int>& nums1, int idx1, vector<int>& nums2, int idx2) {
        if (idx1 == nums1.size()) return false;
        if (idx2 == nums2.size()) return true;
        if (nums1[idx1] < nums2[idx2]) return false;
        if (nums1[idx1] > nums2[idx2]) return true;
        return compare(nums1, idx1 + 1, nums2, idx2 + 1);
    }
};

刷题总结

最近遇到的题目难度都很大，但是非常有意义，希望小伙伴们认真做题，认真总结。