321.拼接最大数

题目来源：https://leetcode-cn.com/problems/create-maximum-number/

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:

nums1 = [3, 4, 6, 5]

nums2 = [9, 1, 2, 5, 8, 3]

k = 5

输出:

[9, 8, 6, 5, 3]

示例 2:

输入:

nums1 = [6, 7]

nums2 = [6, 0, 4]

k = 5

输出:

[6, 7, 6, 0, 4]

示例 3:

输入:

nums1 = [3, 9]

nums2 = [8, 9]

k = 3

输出:

[9, 8, 9]

解法

Step I：分别求两个数组的最大顺序子序列（分治）

假设从nums1取出长度为s的最大顺序子序列，那么nums2中应该取出长度为k-s的最大顺序子序列。问题是如何才能取出子序列保证其字典序最大？

这里引入一个单调栈的概念，该栈维护的是一块有序的数据单元。下面以一个例子说明单调栈的实现：假设从nums1=[5,9,7,6,8,5,2,4]取出长度为s=5的最大顺序子序列，nums1中有8个元素，这意味着我们需要丢弃drop = 8-5 = 3个元素。遍历nums1中的元素，单调栈的内容变化如下：

Step	0	1	2	3	4	drop	instruction
1	5	X	X	X	X	3	栈为空，push(5)
2	9	X	X	X	X	2	栈顶元素5 < 9，pop(5)，栈空，push(9)，drop–
3	9	7	X	X	X	2	栈顶元素9>7，push(7)
4	9	7	6	X	X	2	栈顶元素7>6，push(6)
5	9	7	X	X	X	1	栈顶元素6<8，pop(6)，栈非空，drop–
6	9	X	X	X	X	0	栈顶元素7<8，pop(7)，栈非空，drop–
7	9	8	X	X	X	0	drop == 0 直接push(8)
8	9	8	5	X	X	0	drop == 0 直接push(5)
9	9	8	5	2	X	0	drop == 0 直接push(2)
10	9	8	5	2	4	0	drop == 0 直接push(4)

由此可得nums1数组中的大小为5的最大顺序子序列为9 8 5 2 4 。

而单调栈可以使用vector数据结构表示，具体实现如下：

// 模拟单调栈
// vector<int> maxKSequence(vector<int> nums, int s)
vector<int> stack;
length = nums.size();
int drop = length - s; // s为选取的最大顺序子序列大小
for(int i=0;i<length;i++){
    while( !stack.empty() && nums[i]>stack.back() && drop>0){
        drop--;
        stack.pop_back();
    }
    stack.push_back(nums[i]);
}

Step II：将两个数组对应的最大顺序子序列合并（归并）

假设stack1为nums1的大小为s的最大顺序子序列，stack2为nums2的大小为k-s的最大顺序子序列，接下来就是要将这两个子序列按照字典序归并。即采用双指针按序遍历两个序列，将指针指向字典序大的序列并将该序列的第一个数字插入到新序列中，并将该指针后移一位，以此类推，直至遍历完所有序列。

假设stack1序列为7,8,3,2,1，stack2序列为6,8,2,1，则合并后的序列为7,8,6,8,3,2,2,1,1：

字典序的比较可以使用C++ STL函数lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);，该函数用于按字典序比较两个序列，当 (first1,last1)序列字典序小于(first2,last2)字典序时返回true，反之false。具体实现如下：

vector<int> stack1 = maxKSequence(nums1, s);  // 找nums1长度为s的最大序列
vector<int> stack2 = maxKSequence(nums2, k - s); // 找nums2长度为k-s的最大序列
auto iter1 = stack1.begin(), iter2 = stack2.begin();
while(iter1!=stack1.end() || iter2!=stack2.end()){
	newSeq.push_back(lexicographical_compare(iter1, stack1.end(), iter2, stack2.end()) ? *iter2++ : *iter1++);  // newSeq为新序列
}

Step III：遍历所有可能性，比较找到字典序最大的序列

遍历所有可能的s与k-s，得到两个数组的最大顺序子序列并合并，比较每一对(s，k-s)合并后子序列的字典序，返回字典序最大的序列。

最终代码如下（C++）：

class Solution {
private:
    vector<int> maxKSequence(vector<int> n, int k){
        int n_size = n.size();
        vector<int> res;  // 模拟单调栈
        int drop = n_size - k;
        for(int i=0; i<n_size; i++){
            while(!res.empty() && res.back() < n[i] && drop>0 ){
                drop--;
                res.pop_back();
            }
            res.push_back(n[i]);
        }
        res.resize(k);
        return res;
    }
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> result(k,0);
        int n1 = nums1.size(), n2 = nums2.size();
        for(int s = max(0, k-n2); s <= min(k, n1); s++){
            vector<int> temp1 = maxKSequence(nums1, s);  // 找nums1长度为s的最大序列
            vector<int> temp2 = maxKSequence(nums2, k - s); // 找nums2长度为k-s的最大序列
            // 比较字典序并合并
            vector<int> temp;
            auto iter1 = temp1.begin(), iter2 = temp2.begin();
            while(iter1!=temp1.end() || iter2!=temp2.end()){
                temp.push_back(lexicographical_compare(iter1, temp1.end(), iter2, temp2.end()) ? *iter2++ : *iter1++);
            }
            result = lexicographical_compare(result.begin(), result.end(), temp.begin(), temp.end()) ? temp : result;
        }
        return result;
    }
};

复杂度分析：

时间复杂度：O(k(m+n+k^2)) O(k^2)为归并的时间复杂度，外层最多进行k轮的循环，O(m+n)为寻找两个数组最大序列的时间复杂度。

空间复杂度：O(k)