【一天一大 lee】拼接最大数 (难度:困难) - Day20201202

输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]

输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]

输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[]}
 */
var maxNumber = function(nums1, nums2, k) {
    let _result = [],
        map1 = findMax(nums1, k),
        map2 = findMax(nums2, k),
        max = 0

    // 枚举x、y的可能组合
    for (let x = 0; x <= k; x++) {
        const y = k - x
        if (x <= nums1.length && y <= nums2.length) {
            const merge = mergeMax(map1.get(x) || [], map2.get(y) || [], k)
            const num = merge.join('')
            if (num > max) {
                max = num
                _result = merge
            }
        }
    }
    // 1. 单调栈：从数组重取出 x 个元素，使取出的元素组成的数字最大
    function findMax(nums, k) {
        let len = nums.length,
            map = new Map()
        if (len === 0) return map
        for (let i = 1; i <= k; i++) {
            let stack = [nums[0]]
            for (let j = 1; j < len; j++) {
                // 新元素大于栈底元素，且后面剩余的元素大于填满本轮栈的所需个数
                while (
                    nums[j] > stack[stack.length - 1] &&
                    len - j > i - stack.length
                ) {
                    stack.pop()
                }
                if (stack.length < i) {
                    stack.push(nums[j])
                }
            }
            // 选择个数 -> 最大组合
            map.set(i, stack)
        }
        return map
    }
    // 2. 从两个栈顶开始，每次取栈顶较大的元素
    function mergeMax(stack1, stack2, k) {
        if (!stack1 || !stack2) return stack1 || stack2
        let result = []
        while (stack1.length > 0 || stack2.length > 0) {
            if (stack1.length === 0) return [...result, ...stack2]
            if (stack2.length === 0) return [...result, ...stack1]
            if (stack1.join('') >= stack2.join('')) {
                result.push(stack1.shift())
            } else {
                result.push(stack2.shift())
            }
        }
        return result
    }

    return _result
}