Strictly O(NK) C++ Solution with detailed explanation
\n\tclass list1\n    {\n        vector a;\n        vector> f;\n    public:\n        list1() = delete;\n        inline int size() {return a.size();}\n        inl
\n\tclass list1\n    {\n        vector<int> a;\n        vector<vector<int>> f;\n    public:\n        list1() = delete;\n        inline int size() {return a.size();}\n        inline int next(int x,int d) {return f[x][d];}\n        list1(vector<int>& a0)\n        {\n            a = a0;\n            f = vector<vector<int>>(a0.size() + 1,vector<int>(10,INT_MAX));\n            for (int i = 0;i<a0.size();i++)\n            {\n                f[i][a[i]] = i;\n                for (int j = i-1;j>=0;j--)\n                {\n                    if (a[j] == a[i]) break;\n                    f[j][a[i]] = i;\n                }\n            }\n        }\n    };\n    \n    //dmd for detect_max_digit\n    // dmd(a,x,rem) -> (max_digit, pos) , where a[pos-1] == max_digit\n    // list a , from x, need rem numbers, x not included.\n        \n    pair<int,int> dmd(list1& a,int x,int rem)\n    {\n        for (int d = 9;d >= 0;d--)\n        {\n            int pos = a.next(x,d);\n            if (pos == INT_MAX) continue;\n            if (a.size() - (pos + 1) >= rem)\n            return make_pair(d,pos + 1);\n        }\n    }\n    \n    \n    class Solution {\n    public:\n        vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n            list1 a1 = list1(nums1);\n            int N1 = nums1.size();\n            list1 a2 = list1(nums2);\n            int N2 = nums2.size();\n            \n            auto ret = vector<int>(k,0);\n            auto f = vector<int>(N1 + 1,0); \n            //f[i] denote a1[0..i-1] need a2[0..f[i]-1] to reach the current maximal number, and can expand to length k\n            // in other words, the state is : the number is current maximal and can be expanded, list1 begin with a1[i] and list2 with a2[f[i]] \n            for (int d = 1;d <= k;d++)\n            {\n                int maxDigit = -1;\n                auto tmpf = vector<int>(N1 + 1,INT_MAX);\n                for (int x = 0;x<=N1;x++)\n                {\n                    int y = f[x];\n                    if (y == INT_MAX) continue;\n                    auto m1 = dmd(a1,x,k-d-(N2-y)); \n                    auto m2 = dmd(a2,y,k-d-(N1-x));\n                    maxDigit = max(maxDigit,m1.first);\n                    maxDigit = max(maxDigit,m2.first);\n                }\n                ret[d-1] = maxDigit;\n                for (int x = 0;x<=N1;x++)\n                {\n                    int y = f[x];\n                    if (y == INT_MAX) continue;\n                    auto m1 = dmd(a1,x,k-d-(N2-y));\n                    if (m1.first == maxDigit)\n                    tmpf[m1.second] = min(tmpf[m1.second],y);\n                    auto m2 = dmd(a2,y,k-d-(N1-x));\n                    if (m2.first == maxDigit)\n                    tmpf[x] = min(tmpf[x],m2.second);\n                }\n                f = tmpf;\n            }\n            return ret;\n        }\n    };\n\nAny Question is welcome and will be answered as soon as possible.\nDetailed explanation is coming soon!\nYou may firstly read my code, it\'s quite easy to understand.\n\n## Detailed Solution ##\nLet a1,a2 be the two list from where we construct the maximal number.\nLet N1,N2 denote the size of a1,a2.\nWe construct the maximal number digit by digit.\n\nSuppose we are constructing the d-th digit(ret[0..d-1] is done)  and we have a set of states S = {(a1,b1),(a2,b2),...(a_N,b_N)},For each state (x,y) in S, it means we use a1[0..(x-1)] and a2[0..(y-1)] to construct ret[0..d-1] and a1[x..N1] and a2[y..N2] are avaliabe to construct the remaining digits.\n\nIn the iteration, we need to construct the d-th digit as well as the set S\', that is from where we can construct the d+1-th digit.\n\nFor every state (x,y) in S, we use the function "dmd" to obtain the biggest d-th digit we can get from it. \nLet maxdigit = {max(dmd(x,y)[1])|(x,y) in S}, it is the d-th digit.\n\nAs we now the d-th digit,\nWe scan S again,\nFor every state (x,y) in S, we use the function "dmd" to obtain the (x\',y) and (x,y\') it extands to, \nif a1[x\'-1] == maxdigit, we add (x\',y) to S\'.\nif a2[y\'-1] == maxdigit, we add (x,y\') to S\'.\n\nNow we can construct the d+1-th digit from S\', note that the size of S\' is at most N1, for(x,y1) and (x,y2), y1 < y2, (x,y2) is needless to be recorded.\n\nFinally I\'d like to use an typical example to illustrate the process.\n\n> a1 = [8,1] a2 = [8,9] k = 4\n> \n> S = {(0,0)}\n\nthe first digit is 8,\n\n> S\' = {(0,1),(1,0)}\n\nthe second digit is 9, we construct it from (0,1)\n\n>S\'\' = {(0,2)}\n\nthe remain digits are 8 and 1,\nwe finally reach 8981.\n\nNow I use python and write a piece of much shorter and more readable code as follows:\n\n ```\nclass Solution:\n    \n    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n        \n        def calcnext(a):\n            ret = [[-1] * 10 for i in range(len(a) + 1)]\n            for i in reversed(range(len(a))):\n                for d in range(0, 10):\n                    ret[i][d] = i if a[i] == d else ret[i + 1][d]\n            return ret\n        \n        M, N = len(nums1), len(nums2)\n        next1 = calcnext(nums1)\n        next2 = calcnext(nums2)\n        ret = []\n        S = [(0, 0)]\n        \n        for i in range(k):\n            rem = k - i - 1\n            found, best = False, [N + 1] * (M + 1)\n            for d in reversed(range(0, 10)):\n                for (d1, d2) in S:\n                    n1 = next1[d1][d] + 1\n                    if n1 and M - n1 + N - d2 >= rem:\n                        found, best[n1] = True, min(best[n1], d2)\n                    n2 = next2[d2][d] + 1\n                    if n2 and M - d1 + N - n2 >= rem:\n                        found, best[d1] = True, min(best[d1], n2)\n                if found:\n                    ret += [d]\n                    break\n            S = [(i, best[i]) for i, x in enumerate(best) if best[i] <= N]\n\n        return ret\n\n\n
[]