Участник:Rashit/Create Max Number

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/create-maximum-number

 
class Solution {
 
   public:
   vector<int> maxArray(vector<int>& nums, int k) {
        vector<int> array(k, 0);
        for (int i = 0, j = 0; i < nums.size(); ++i) {
            while (nums.size() - i + j > k && j > 0 && array[j - 1] < nums[i]) --j;
                if (j < k) array[j++] = nums[i];
        }
        return array;
    }
    bool maximum(vector<int>& nums1, int i, vector<int>& nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
                ++i;
                ++j;
        }
        return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
    }
    vector<int> sort(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> array(k, 0);
        for (int i = 0, j = 0, r = 0; r < k; ++r)
            array[r] = maximum(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
         return array;
    }
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
         if (k == 0) return {};
         vector<int> res;
         for (int i = max(0, k - (int)nums2.size()); i <= k && i <= nums1.size(); ++i) {
            vector<int> array1 = maxArray(nums1, i);
            vector<int> array2 = maxArray(nums2, k - i);
            vector<int> data = sort(array1, array2, k);
            if (maximum(data, 0, res, 0)) res = data;
         }
         return res;
    }};