Create Maximum Number

Problem: Create Maximum Number

The solution can be split into two parts.

First, to form a number of length n, we can get i numbers from number A and k-i numbers from number B, as long as we do not exceed length of arguments. Thus, we can try all the combinations to get the answer.

Then, once we set the length we want, we can use greedy approach. What we care about is how many numbers we can drop. We use a stack to maintain the result. As long as we still can drop numbers, we pop numbers smaller than current from the stack. For example, if we want 3 elements from [9, 1, 2, 5, 8, 3], we can drop 3 numbers. We first push 9 and 1 into the stack, then we find 2 is bigger than 1 so we drop 1, which makes us only 2 numbers left to drop. When we are pushing 5, we will drop 2 and we will drop 5 for 8. By this method, we can try our best to make bigger numbers appear at higher base.

Code in Python:

class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        def drop(nums, k):
            x = len(nums) - k
            stack = []
            for num in nums:
                while stack and stack[-1] < num and x:
                    stack.pop()
                    x -= 1
                stack.append(num)
            return stack[:k]

        def merge(nums1, nums2):
            return [max(nums1, nums2).pop(0) for _ in nums1+nums2]

        return max(merge(drop(nums1, i), drop(nums2, k-i)) for i in xrange(k+1) if i <= len(nums1) and k-i <= len(nums2))