321. Create Maximum Number

Given two arrays of lengthmandnwith digits0-9representing two numbers. Create the maximum number of lengthk <= m + nfrom digits of the two. The relative order of the digits from the same array must be preserved. Return an array of thekdigits. You should try to optimize your time and space complexity.

Example 1:

nums1 =[3, 4, 6, 5]
nums2 =[9, 1, 2, 5, 8, 3]
k =5
return[9, 8, 6, 5, 3]

Example 2:

nums1 =[6, 7]
nums2 =[6, 0, 4]
k =5
return[6, 7, 6, 0, 4]

Example 3:

nums1 =[3, 9]
nums2 =[8, 9]
k =3
return[9, 8, 9]

S: DP

对单个数组，dp[i]表示由i个元素组成的最大数列

要求两数组组成的长度为k的最大数列可以转化为求dp1[i]和dp2[k-i]组成的最大数列，two poniter merge即可（注意当两指针所指元素相同时，要根据量数列后续数字决定前进哪个指针）

求dp[i]可以由大到小删除元素得到，例如数组[7,3,5,6,1] dp[5]即原数组，dp[4]由dp[5]删除一个数得到，

要找到应该删的数：从头开始维护一个递减数列，找到第一个违反递减数列的数(5)，删除它前一个数(3).循环直到整个数组都是一个递减数列，之后一次删掉最后一个元素即可

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<vector<int>> dp1(n1 + 1), dp2(n2 + 1);
        dpinit(nums1, dp1);
        dpinit(nums2, dp2);
        vector<int> result;
        for (int i = 0; i <= k && i <= n1 && k - i >= 0; ++i) {
            if (k - i > n2) continue;
            vector<int> candidate = merge(dp1[i], dp2[k - i]);
            if (result.empty() || smaller(result, candidate)) result = candidate;
        }
        return result;
    }

    void dpinit(vector<int> nums, vector<vector<int>>& dp) {
        int idx = nums.size();
        int pre = 0;
        dp[idx--] = nums;
        while (idx > 0) {
            dp[idx] = dp[idx + 1]; //在dp[idx + 1]中删除一个数得到dp[idx]
            //找到dp[idx + 1]第一个违反递减数列的数, 它前一个数即为要删除的数
            while (pre == 0 || (pre < dp[idx].size() && dp[idx][pre] <= dp[idx][pre - 1])) {
                pre++;
            }
            if (pre == dp[idx].size()) break;
            pre--;
            dp[idx].erase(dp[idx].begin() + pre);
            idx--;
        }
        while (idx >= 0) {  //dp[idx + 1]已是递减数列，之后只用依次删除末尾元素
            dp[idx] = dp[idx + 1];
            dp[idx].pop_back();
            idx--;
        }
    }

    vector<int> merge(vector<int> vec1, vector<int> vec2) {
        int n1 = vec1.size(), n2 = vec2.size();
        int i1 = 0, i2 = 0, idx = 0;
        vector<int> result(n1 + n2);
        while (i1 < n1 && i2 < n2) {
            if (greater(vec1, vec2, i1, i2)) {  //当两数相同时要比较它们之后的序列
                result[idx++] = vec1[i1++];
            } else {
                result[idx++] = vec2[i2++];
            } 
        }
        while (i1 < n1) result[idx++] = vec1[i1++];
        while (i2 < n2) result[idx++] = vec2[i2++];
        return result;
    }

    bool smaller(vector<int> res, vector<int> cand) { 
        for (int i = 0; i < res.size(); ++i) {
            if (res[i] < cand[i]) return true;
            if (res[i] > cand[i]) return false;
        }
        return false;
    }

    bool greater(vector<int>& vec1, vector<int>& vec2, int i1, int i2) {  //vec1 > vec2
        while (i1 < vec1.size() && i2 < vec2.size()) {
            if (vec1[i1] > vec2[i2]) return true;
            if (vec1[i1] < vec2[i2]) return false;
            i1++;
            i2++;
        }
        return i2 == vec2.size();
    }
};