321. Create Maximum Number - cocoder39/coco39_LC GitHub Wiki

321. Create Maximum Number

  1. get the max sub vector from nums1 whose length is i
  2. get the max sub vector from nums2 whose length is k - i
  3. merge the two sub vectors

tips:

  • 0 <= i <= m && 0 <= k - i <= n, thus i >= 0 && i >= k -n, i <= m && i <= k
  • use operator > to compare the contents of two vectors lexicographically. The complexity is up to linear in the smaller size, which is different from following code. An example is when merging [6, 7] with [6, 0, 4], one result is [6, 6, 7, 0, 4] while correct answer is [6, 7, 6, 0, 4]
vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        int i = 0, j = 0;
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] <= nums2[j]) {
                res.push_back(nums2[j++]);
            }
            else {
                res.push_back(nums1[i++]);
            }
        }
        if (i < nums1.size())
            res.insert(res.end(), nums1.begin() + i, nums1.end());
        else
            res.insert(res.end(), nums2.begin() + j, nums2.end());
        return res;
    }
  • following code is very cool, it returns the max vector with size k once meet a num which is greater than res.back(), you may either push it back or drop it. It depends on if you have enough num to drop, which is guided by drop. If the nums is in descending order, then all nums would be pushed back and the size may exceed k. Therefore res.resize(k) is essential. Same idea is used to solve remove duplicate letters 
vector<int> maxsub(vector<int>& nums, int k) {
        int drop = nums.size() - k;
        vector<int> res;
        for (auto num : nums) {
            while (drop > 0 && res.size() != 0 && res.back() < num) {
                res.pop_back();
                drop--;
            }
            res.push_back(num);
        }
        res.resize(k);
        return res;
    }

time complexity is O((m + n) ^ 3)

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        vector<int> res(k);
        //0 <= i <= m
        //0 <= k - i <= n
        for (int i = max(0, k - n); i <= min(m, k); i++) { //O((m + n) ^ 3)
            vector<int> res1 = maxNum(nums1, i); //O(m)
            vector<int> res2 = maxNum(nums2, k - i); //O(n)
            res = max(res, merge(res1, res2)); //O(k ^ 2) <= O((m + n) ^ 2)
        }
        return res;
    }
private:
    vector<int> maxNum(vector<int>& nums, int k) {
        vector<int> res;
        //number of digits that can be dropped
        int drop = nums.size() - k;
        for (int i = 0; i < nums.size(); i++) { //O(n)
            while (! res.empty() && nums[i] > res.back() && drop > 0) {
                res.pop_back();
                drop--;
            }
            res.push_back(nums[i]);
        }
        res.resize(k);
        return res;
    }
    
    vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector<int> res(m + n);
        for (int i = 0; i < m + n; i++) { //O((m + n) ^ 2)
            vector<int>& tmp = nums1 > nums2 ? nums1 : nums2;
            res[i] = tmp[0];
            tmp.erase(tmp.begin());
        }
        return res;
    }
};
⚠️ **GitHub.com Fallback** ⚠️