321. 拼接最大数

题目：

给定长度分别为 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/create-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：吃了炫迈的单调栈

如果给定一个数组这个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序，然后我们求长度为k最大的数，我们可以维持单调递减栈（保证第一个数最大），但这样不一定能凑齐k个数，所以我们要当k减去栈中元素个数等于数组剩下元素的个数时直接将数组中的元素全部放到栈中，这样我们就能确保得到一个长度为k的最大的数。而题目中给我们两个数组，我们就需n1中选x个数保证最优（长度为x且最大）从n2中选y个（同）数，且x+y=k，得到这两组数后，将这两组数合并，然后与之前的结果比较。

注意：这里合并时，如果两个元素相等我们不能随便从n1或n2中选一个，而是需要接着比较下去直到不相同或一个数组已经到了末尾。

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
       int[] ans = new int[k];
        int n = nums1.length;
        int m = nums2.length;
        /*nums1 - end : 结束长度 i : 开始长度 如果nums2可以组成长度为k的单调栈则从nums1中选的长度可从0开始*/
        int end = Math.min(k, n);
        for(int i = Math.max(0, k - m); i <= end; i++) {
            int[] n1 = getStack(nums1, i, n);
            int[] n2 = getStack(nums2, k - i, m);
            int[] cur = merge(n1, n2, k);
            if(compare(ans, cur, 0, 0)){
                ans = cur;
            }
        }
        return ans;
    }

    private boolean compare(int[] ans, int[] cur, int i, int j) {
        int n = ans.length, m = cur.length;
        while(i < n && j < m) {
            if(ans[i] < cur[j]) return true;
            else if(ans[i] > cur[j]) return false;
            i++;
            j++;
        }
        return n - i < m - j;
    }

    private int[] merge(int[] n1, int[] n2, int k) {
        int[] res = new int[k];
        int ind = 0;
        int n = n1.length, i = 0;
        int m = n2.length, j = 0;
        while(i < n && j < m) {
            if(compare(n1, n2, i, j)) res[ind++] = n2[j++];
            else res[ind++] = n1[i++];
        }
        while(i < n) res[ind++] = n1[i++];
        while(j < m) res[ind++] = n2[j++];
        return res;
    }

    private int[] getStack(int[] nums, int k, int n) {
        int ind = 0;
        int[] res = new int[k];
        for(int i = 0; i < n; i++) {
            while(ind != 0 && nums[i] > res[ind - 1] && n - i > k - ind) {
                ind--;
            }
            if(ind < k)
                res[ind++] = nums[i];
        }
        return res;
    }
}