[LeetCode] 321. Create Maximum Number

 Problem : https://leetcode.com/problems/create-maximum-number/

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        
        def monotoneDecreasingSequence(nums, size):
            if size <= 0: return []
            
            dropCount = len(nums) - size
            
            result = []
            
            for n in nums:
                while result and result[-1] < n and dropCount > 0:
                    result.pop()
                    dropCount -= 1
                    
                result.append(n)
            
            return result[:size]
    
    
        def merge(n1, n2):
            i = j = 0
            result = []
            while i < len(n1) or j < len(n2):
                if i < len(n1) and j < len(n2):
                    # important! compare the rest numbers in lexical 
                    if n1[i:] > n2[j:]:
                        result.append(n1[i])
                        i += 1
                    else:
                        result.append(n2[j])
                        j += 1
                elif i < len(n1):
                    result.append(n1[i])
                    i += 1
                else:
                    result.append(n2[j])
                    j += 1
            
            return result
        
        result = []
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) +1):
            mds1 = monotoneDecreasingSequence(nums1, i)
            mds2 = monotoneDecreasingSequence(nums2, k - i)
            merged = merge(mds1, mds2)
            
            result = max(result, merged)
        
        return result