321. Create Maximum Number

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• 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;
        }
    }
}