• ㊗️
• 大家
• offer
• 多多！

## Problem

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]


Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]


Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]


## Code

class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int len1 = nums1.length;
int len2 = nums2.length;
int[] res = new int[k];

// 如果 k > len2 证明一定要在num1中取到数字才可以
// 如果 k > len1 那么 i <= len1 证明最多可以把nums1全部取到
// 如果 k < len1 那么 i <= k 证明在nums1中最多能取k个元素
for(int i = Math.max(0, k - len2); i <= Math.min(k, len1); i++){
// nums1取i个
// nums2取k - i个
int[] max1 = maxArray(nums1, i);
int[] max2 = maxArray(nums2, k - i);

int[] mergeMax = merge(max1, max2, k);
if(greater(mergeMax, 0, res, 0)){
res = mergeMax;
}
}
return res;
}

// 在一个数组中，不改变顺序的条件下，能取到的最大数字
private int[] maxArray(int[] nums, int k){
int[] res = new int[k];
int remove = nums.length - k;

Stack<Integer> stack = new Stack<>();

for(int i = 0; i < nums.length; i++){
while(!stack.isEmpty() && nums[i] > stack.peek() && remove > 0){
stack.pop();
remove--;
}

stack.push(nums[i]);
}

while(remove != 0){
stack.pop();
remove--;
}

for(int i = k - 1; i >= 0; i--){
res[i] = stack.pop();
}
return res;
}

private int[] merge(int[] nums1, int[] nums2, int k){
int[] res = new int[k];
int index1 = 0;
int index2 = 0;
for(int i = 0; i < k; i++){
// 哪个可能组成的数字更大就先放哪个
res[i] = greater(nums1, index1, nums2, index2) ? nums1[index1++] : nums2[index2++];
}

return res;
}

// 两个数组的数字谁放在前边更大
private boolean greater(int[] nums1, int i, int[] nums2, int j){
while(i < nums1.length && j < nums2.length && nums1[i] == nums2[j]){
i++;
j++;
}

// nums2排空了，nums1还有，因此nums1更大
if(j == nums2.length){
return true;
// 出现了nums1[i] != nums2[j]的情况
// 此时如果nums1[i] > nums2[j]返回true
} else if (i < nums1.length && nums1[i] > nums2[j]){
return true;
} else {
return false;
}
}
}