题目描述
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例 1:
输入: nums1 =[3, 4, 6, 5]nums2 =[9, 1, 2, 5, 8, 3]k =5输出:[9, 8, 6, 5, 3]
示例 2:
输入: nums1 =[6, 7]nums2 =[6, 0, 4]k =5输出:[6, 7, 6, 0, 4]
示例 3:
输入: nums1 =[3, 9]nums2 =[8, 9]k =3输出:[9, 8, 9]
https://leetcode-cn.com/problems/create-maximum-number/
解法1
解法1采用分治法。我们将问题“找到长度为k的值最大的数组”，拆分成两个子问题。
- 子问题1.1 – 在nums1中寻找i个数maxSub1，使得maxSub1最大
- 子问题1.2 – 在nums2中寻找j个数maxSub2，使得maxSub2最大
- 备注：i + j = k, 且 0 <= i <= |nums1|, 0 <=j <= |nums2|
- 子问题2 – 合并maxSub1与maxSub2使得合并的结果最大。
子问题1
我们先解决子问题1，我们将解决子问题1的函数定义为int[] maxArray(int[] nums, int k) ，表示从nums中保证顺序地选取k个数字，使得该数字最大。
子问题1可以使用贪心法解决。我们使用一个大小为k的栈，遍历nums的每个元素：先出栈，如果当前元素大于栈顶就持续出栈，直到当前元素小于等于栈顶或者nums剩余的元素无法填满栈；再压栈，如果栈未满则压栈。栈按照这种策略更新，能够保证取到k个数，且从栈底到栈顶组成的数能够保证最大。
private int[] maxArray(int[] nums, int k) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
while (nums.length - i + stack.size() > k && !stack.isEmpty() && stack.peek() < curr)
stack.pop();
if (stack.size() < k)
stack.push(curr);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = stack.get(i);
}
return res;
}
子问题2
我们将解决子问题2的函数定义为int[] merge(int[] nums1, int[] nums2)。如果nums1中的数字与nums2中的数字没有重复，那么算法的实现很简单，我们优先选取nums1与nums2中最大的数字。例如，nums1 = [5,3,1], nums2 = [6,4,2]，合并后的最大数字为[6,5,4,3,2,1]。
但如果两个数组中出现重复的数字呢？例如，nums1 = [6, 7], nums2 = [6,0,4]。对于这种case，当出现nums[i] == nums[j]时，我们应该看i与j后面的数字哪一个大，选取nums[i+1]与nums[j+1]大的那一个；但如果nums[i+1]与nums[j+1]也相等呢？我们应该持续比较，直到发现nums[i+1…end]与nums[j+1…end]不相等，然后选取大的那一个数组。
private int[] merge(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
int[] res = new int[n];
int r = 0, i = 0, j = 0;
while (r < n) {
res[r++] = greater(nums1, nums2, i, j) ? nums1[i++] : nums2[j++];
}
return res;
}
private boolean greater(int[] nums1, int[] nums2, int i, int j) {
while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
合并子问题1与子问题2的解
我们已经有了子问题1与子问题2的解法了，将他们合并就能得到问题的答案。我们以此计算从nums1找i个数构成maxSub1，nums2找j个数构成maxSub2（i+j = k），然后用子问题2的解法合并maxSub1与maxSub2，得到currMax. 当i与j变化的时候，使用计算出的currMax不断地更新res变量。当i与j去得到所有可能值后，res变量就是答案。
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[] res = new int[k];
for (int i = 0; i <= k; i++) {
if (i <= nums1.length && (k - i) <= nums2.length) {
int[] maxSub1 = maxArray(nums1, i);
int[] maxSub2 = maxArray(nums2, (k - i));
int[] currMax = merge(maxSub1, maxSub2);
if (greater(currMax, res, 0, 0))
res = currMax;
}
}
return res;
}
全部代码：
import java.util.Stack;
class Solution {
int[] maxArray(int[] nums, int k) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
while (nums.length - i + stack.size() > k && !stack.isEmpty() && stack.peek() < curr)
stack.pop();
if (stack.size() < k)
stack.push(curr);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = stack.get(i);
}
return res;
}
private int[] merge(int[] nums1, int[] nums2) {
int n = nums1.length + nums2.length;
int[] res = new int[n];
int r = 0, i = 0, j = 0;
while (r < n) {
res[r++] = greater(nums1, nums2, i, j) ? nums1[i++] : nums2[j++];
}
return res;
}
private boolean greater(int[] nums1, int[] nums2, int i, int j) {
while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[] res = new int[k];
for (int i = 0; i <= k; i++) {
if (i <= nums1.length && (k - i) <= nums2.length) {
int[] maxSub1 = maxArray(nums1, i);
int[] maxSub2 = maxArray(nums2, (k - i));
int[] currMax = merge(maxSub1, maxSub2);
if (greater(currMax, res, 0, 0))
res = currMax;
}
}
return res;
}
}
参考：
https://web.archive.org/web/20160120093629/http://algobox.org/create-maximum-number/