题目描述

给定长度分别为 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/

Leave a Reply

Your email address will not be published. Required fields are marked *