LeetCode-321 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.

Note: You should try to optimize your time and space complexity.

题目大意

两个数组长度分别为m和n，要求组成一个新的长度为k（k <= m + n）的数组，要求数组中所有数字表示的正整数最大（即数组为num[] = {1,2,3}则代表n = 123）。

（注意同一个数组中的数字的前后相对顺序不能改变）

示例

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

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

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

解题思路

基于暴力枚举的思想，外层循环遍历所有的第一个数组可能提供的数字的个数，在循环中依次求得第一个数组中取i个最大的数字，第二个数组取k-i个最大的数字，再将两个数组合并为一个，取所有循环结果的最大值。

复杂度分析

时间复杂度：O(N²)

空间复杂度：O(N)

代码

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res;
        int m = nums1.size(), n = nums2.size();
        // 从nums1中取出i个数字，nums2中取出k-i个数字
        for(int i = max(0, k - n); i <= min(k, m); ++i) {
            res = max(res, maxNum(maxNum(nums1, i), maxNum(nums2, k - i)));
        }
        
        return res;
    }
    // 从数组中取出k个能组成的最大的相对顺序不变的数字
    vector<int> maxNum(vector<int> num, int k) {
        // drop代表需要从该数组中淘汰的数字的个数
        int drop = num.size() - k;
        vector<int> res;
        
        for(int n : num) {
            // 当淘汰数不为0且res的最后一个数字小于当前数字时，替换掉最后一个数字
            while(drop && res.size() && res.back() < n) {
                res.pop_back();
                --drop;
            }
            res.push_back(n);
        }
        
        res.resize(k);
        return res;
    }
    // 将两个数组按照相对顺序不变进行合并，得到最大的数值
    vector<int> maxNum(vector<int> num1, vector<int> num2) {
        vector<int> res;
        while(num1.size() + num2.size()) {
            vector<int>& tmp = num1 > num2 ? num1 : num2;
            res.push_back(tmp[0]);
            tmp.erase(tmp.begin());
        }
        
        return res;
    }
};