python 1 hard = 2 easy + 1 medium problems
Intuition\n Describe your first thoughts on how to solve this problem. \nIf there is only one array, how to solve it, use monotonic stack.\nIf we can find subar
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf there is only one array, how to solve it, use monotonic stack.\nIf we can find subarray in nums1 and nums2, then merge them.\nThe ans is all combinations of the merge\n# Approach\n<!-- Describe your approach to solving the problem. -->\nmonotonic stack is a medium problem\nmerge is an easy one\nfind combination should be an easy problem.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nk* O(n^2)\n\nmonotonic stack is O(n)\nmerge is O(n)\nk loops\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution:\n    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n        def getMaxOrder(nums, n, total, res): # monotonic stack\n            for i, v in enumerate(nums):\n                while res and len(res) + total - i > n and res[-1] < v:\n                    res.pop()\n                if len(res) < n:\n                    res.append(nums[i])\n            return res\n\n        def merge(nums1, nums2, ans): # check lexicographically greater\n            while nums1 or nums2:\n                if nums1 > nums2:\n                    ans.append(nums1[0])\n                    nums1 = nums1[1:]\n                else:\n                    ans.append(nums2[0])\n                    nums2 = nums2[1:]\n            return ans\n\n        n1, n2 = len(nums1), len(nums2)\n        res = []\n        for i in range(max(0, k - n2), min(k, n1) + 1): # find all combinations of nums1 and nums2\n            ans = merge(getMaxOrder(nums1, i, n1, []), getMaxOrder(nums2, k - i, n2, []), [])\n            res = max(ans, res)\n        return res\n```
['Python3']