Buckle practice - maximum number of 28 splices

28 Maximum number of stitches

1. Problem description
The given lengths are respectively m and n Two arrays of , Its elements are composed of 0-9 constitute , Represents the number on each bit of two natural numbers . Now choose from these two arrays k (k <= m + n) Put the numbers together to make a new number , It is required that the numbers taken from the same array keep their relative order in the original array .

Find the maximum number that satisfies the condition . The result returns a length indicating that the maximum number is k Array of .

explain : Please optimize the time and space complexity of your algorithm as much as possible .

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]

The following can be used: main function ：

int main()

{

int m,n,k,data;

vector<int> nums1,nums2;

cin>>m;

for(int i=0; i<m; i++)

{

    cin>>data;

    nums1.push_back(data);

}

cin>>n;

for(int i=0; i<n; i++)

{

    cin>>data;

    nums2.push_back(data);

}

cin>>k;

vector<int> res=Solution().maxNumber(nums1,nums2,k);

for(int i=0; i<res.size(); i++)

    cout<<res[i];



return 0;

}
2. Enter description
First, enter the length of the array m, Then input m individual 0-9 The number of , The numbers are separated by spaces .

Then enter the array length n, Then input n individual 0-9 The number of , The numbers are separated by spaces .

Finally, enter an integer k.

3. The output shows that
Output result array , There is no space in the output .
4. Example
Input
2
6 7
3
6 0 4
5
Output
67604
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<stack>
using namespace std;

int compare(vector<int>&nums1, int index1, vector<int>&nums2, int index2);

//1. Find monotone stack 
vector<int> GetMonStack(vector<int> &nums, int len)
{
    
	stack<int>s;// Define the result stack s
	int n = nums.size();
	int drop_num = n - len;// Number of elements to be removed 
	// Traverse nums Array , Construct a monotonic stack , For maximum 
	for (int i = 0; i < n; i++)
	{
    
		while (!s.empty() && s.top() < nums[i] && drop_num > 0)// The stack is not empty and the value of the element at the top of the stack is higher than that of the currently traversed nums[i] Small , And the number that needs to be discarded has not reached , Discard the stack top element 
		{
    
			s.pop();
			drop_num--;
		}
		if (s.size() < len)// Pay attention to judge whether it is full before entering the stack 
		{
    
			s.push(nums[i]);// Into the stack, 
		}
		else// Contrary to the previous stack , Elements are discarded 
		{
    
			drop_num--;
		}
	}
	// Stack s The element in is converted to vector type 
	vector<int>res(len,0);
	int i = len - 1;
	while (!s.empty())
	{
    
		res[i--] = s.top();
		s.pop();
	}
	return res;
}




//2. Monotonic stack v1,v2 Merge operation 

vector<int> MergeVector(vector<int> &v1, vector<int> &v2)
{
    
	//1. Calculate the size and judge the special value 
	int size_v1 = v1.size();
	int size_v2 = v2.size();
	if (!size_v1)//v1 It's empty 
		return v2;
	if (!size_v2)//v2 It's empty 
		return v1;
	//2. Compare the maximum values one by one 
	int index1, index2;
	index1 = index2 = 0;
	int i = 0;
	int length = size_v1 + size_v2;
	vector<int>res(length,0);// Define result array 
	// The comparison returns a larger value 
	while (i < length)
	{
    
		if (compare(v1, index1, v2, index2) > 0)
		{
    
			res[i++] = v1[index1++];
		}
		else
			res[i++] = v2[index2++];
	}
	return res;
}

int compare(vector<int>&nums1, int index1, vector<int>&nums2, int index2)
{
    
	int x = nums1.size();
	int y = nums2.size();
	while (index1 < x && index2 < y)// It's not finished 
	{
    
		int tag = nums1[index1++] - nums2[index2++];
		if (tag != 0) return tag;
	}
	return (x - index1) - (y - index2);// One has been traversed  
}


vector<int> maxNumber(vector<int>&nums1, vector<int>&nums2, int k)
{
    
	int size_1 = nums1.size();  
	int size_2 = nums2.size();

	//start and end Respectively represent the constructed v1 Minimum and maximum length of monotone stack 
	int start = max(0, k - size_2); // Understanding ？ To get the number K>v2.size() , explain v1 At least take k-v2.size() Number , To gather up enough K Number 
	int end = min(k, size_1);// if K<size_1() , At most v1 Remove from k Number 

	vector<int>res(k, 0);// Result array 
	for (int i = start; i <= end; i++)
	{
    
		vector<int> v1(GetMonStack(nums1, i));
		vector<int> v2(GetMonStack(nums2, k - i));
		vector<int> tmp(MergeVector(v1, v2));
		if (compare(tmp, 0, res, 0) > 0)
			res.swap(tmp);// Note that there swap() The magic effect of  , Real time updates res To the maximum 
	}
	return res;
}



 
int main()

{
    

	int m, n, k, data;

	vector<int> nums1, nums2;

	cin >> m;

	for (int i = 0; i < m; i++)

	{
    

		cin >> data;

		nums1.push_back(data);

	}

	cin >> n;

	for (int i = 0; i < n; i++)

	{
    

		cin >> data;

		nums2.push_back(data);

	}

	cin >> k;

	vector<int> res = maxNumber(nums1, nums2, k);

	for (int i = 0; i < res.size(); i++)

		cout << res[i];



	return 0;

}