0%

### leetcode Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9] nums2 = [8, 9] k = 3 return [9, 8, 9] 题目地址：leetcode Create Maximum Number

Idea:

To find the maximum ,we can enumerate how digits we should get from nums1 , we suppose it is i.

So ,  the digits from nums2 is K - i.

And we can use a stack to get the get maximum number(x digits) from one array.（just like leetcode Remove Duplicate Letters

OK, Once we choose two maximum subarray , we should combine it to the answer.

It is just like merger sort, but we should pay attention to the case: the two digital are equal.

we should find the digits behind it to judge which digital we should choose now.

In other words,we should judge which subarry is bigger than the other.

That's all.

The algorithm is O((m+n)^3) in the worst case.

If you have any question or suggest, I am happy you can comment on my blog .

Thanks, merry christmas :)

Java 21ms

C++ 60ms

Python 636ms

## 只需要greater函数的解释

• 对于都未到达数组长度的，哪个大选哪个
• 若x1 <  res1.length  ，说明x2到达数组的长度了，选res1 ，因为要给后面的数更早出现的机会

• [3,3,4]  [3,3] k = 5
• 答案为[3,3,4,3,3]
• 选择的过程中，因为第二个到末尾了，第一个还没到，显然4比较大，要给4早出现的机会。所以选res1
• 否则选res2（可能是x2 <  res2.length 也可能是 x1 == res1.length && x2 == res2.length）

## 递归寻找最大子数组

java 150ms,递归寻找效率肯定不如用栈