给定长度分别为?m?和?n?的两个数组，其元素由?0-9?构成，表示两个自然数各位上的数字。现在从这两个数组中选出?k (k <= m + n)?个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为?k?的数组。
说明:?请尽可能地优化你算法的时间和空间复杂度。
示例?1:
输入: nums1 =[3, 4, 6, 5]nums2 =[9, 1, 2, 5, 8, 3]k =5输出:[9, 8, 6, 5, 3]
示例 2:
输入: nums1 =[6, 7]nums2 =[6, 0, 4]k =5输出:[6, 7, 6, 0, 4]
示例 3:
输入: nums1 =[3, 9]nums2 =[8, 9]k =3输出:[9, 8, 9]
//拼接最大数
//求满足条件的最大数
//最大数特点：相同组成的情况下，尽可能的把大数放前面
//最大数的位数已定
//从前往后，前面的数越大的越大
//两个数组拼接
//需要借助分治，假设从两个数组中需要取几个
//改良后的单调栈->栈顶的元素应该更小（注意剩的位数够不够）
#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
vector<int> nums1;//数组1
vector<int> nums2;//数组2
int k;//最终整数数组的位数
vector<int> result;//最终整数数组
stack<int> stk1,stk2;//单调栈
vector<int> t1,t2;//存单调栈中的元素
stack<int> eq;//存相等的栈顶
int n1,n2;//两个数组长度
string maxStr = "0";//记录当前最大的整数
string res;
int cnt;//单调栈和数组中剩下的元素和
int inStack;//单调栈里元素个数
//单调栈
void monotonicStack1(int p,int k1){
while(!stk1.empty()){
if(stk1.top() < nums1[p] && cnt > k1){
stk1.pop();
cnt--;
inStack--;
}else{
break;
}
}
//栈里的元素不能超过k1个
if(inStack < k1){
stk1.push(nums1[p]);
inStack++;
}else{
cnt--;
}
}
void monotonicStack2(int p,int k2){
while(!stk2.empty()){
if(stk2.top() < nums2[p] && cnt > k2){
stk2.pop();
cnt--;
inStack--;
}else{
break;
}
}
//栈里的元素不能超过k2个
if(inStack < k2){
stk2.push(nums2[p]);
inStack++;
}else{
cnt--;
}
}
//分治找各个情况下的
/*void divide(int k1,int k2){
//找第一个数组的元素
//单调栈
cnt = n1;
inStack = 0;
for(int i = 0;i < n1;i++){
monotonicStack1(i,k1);
}
//找第二个数组的元素
//单调栈
cnt = n2;
inStack = 0;
for(int i = 0;i < n2;i++){
monotonicStack2(i,k2);
}
//弹出合并两个栈中的内容
//注意弹出的内容是反向的
while(!stk1.empty()){
//cout << stk1.top();
t1.push(stk1.top());
stk1.pop();
}
//cout<<endl;
while(!stk2.empty()){
//cout << stk2.top();
t2.push(stk2.top());
stk2.pop();
}
//cout<<endl;
while(!t1.empty() && !t2.empty()){
//逻辑错误
int last = -1;
while(!t1.empty() && !t2.empty() && t1.top() == t2.top() && last < t1.top()){
//如果两个栈顶相等，判断下一个哪个更大
//cout<<t1.top();
last = t1.top();
res += to_string(t1.top());
eq.push(t1.top());
t1.pop();
t2.pop();
}
if(t1.empty()){
while(!eq.empty()){
t1.push(eq.top());
eq.pop();
}
continue;
}else if(t2.empty()){
while(!eq.empty()){
t2.push(eq.top());
eq.pop();
}
continue;
}
//将相等的元素放回
if(t1.top() > t2.top()){
while(!eq.empty()){
t2.push(eq.top());
eq.pop();
}
}else if(t1.top() < t2.top()){
while (!eq.empty()) {
t1.push(eq.top());
eq.pop();
}
}else{
continue;
}
if(t1.top() > t2.top()){
//cout<<t1.top();
res += to_string(t1.top());
t1.pop();
}else if(t1.top() < t2.top()){
//cout<<t2.top();
res += to_string(t2.top());
t2.pop();
}
}
while(!t1.empty()){
//cout<<t1.top();
res += to_string(t1.top());
t1.pop();
}
while(!t2.empty()){
//cout<<t2.top();
res += to_string(t2.top());
t2.pop();
}
//cout<<endl;
//maxStr = max(res,maxStr);
maxStr = maxStr > res ? maxStr : res;
//cout<<res<<endl;
//清空字符串
res = "";
}*/
//改用数组合并，逻辑更清楚
void divide(int k1,int k2){
//找第一个数组的元素
//单调栈
cnt = n1;
inStack = 0;
for(int i = 0;i < n1;i++){
monotonicStack1(i,k1);
}
//找第二个数组的元素
//单调栈
cnt = n2;
inStack = 0;
for(int i = 0;i < n2;i++){
monotonicStack2(i,k2);
}
//弹出合并两个栈中的内容
//注意弹出的内容是反向的
while(!stk1.empty()){
//cout << stk1.top();
t1.push_back(stk1.top());
stk1.pop();
}
//cout<<endl;
while(!stk2.empty()){
//cout << stk2.top();
t2.push_back(stk2.top());
stk2.pop();
}
//cout<<endl;
//反转
reverse(t1.begin(),t1.end());
reverse(t2.begin(),t2.end());
/*for(int i = 0;i < k1;i++){
cout<<t1[i];
}
cout<<endl;
for(int j = 0;j < k2;j++){
cout<<t2[j];
}
cout<<endl;*/
int p1 = 0,p2 = 0;//两个数组的遍历指针
while(p1 < k1 && p2 < k2){
if(t1[p1] > t2[p2]){
res += to_string(t1[p1]);
p1++;
}else if(t1[p1] < t2[p2]){
res += to_string(t2[p2]);
p2++;
}else{
//两个元素相等时
res += to_string(t1[p1]);
//找下一个不相等的元素
int i = p1 + 1,j = p2 + 1;
if(i == k1){
//数组1空了
p2++;
continue;
}else if(j == k2){
//数组2空了
p1++;
continue;
}
for(;i < k1,j < k2;i++,j++){
if(t1[i] > t2[j]){
p1++;
break;
}else if(t1[i] < t2[j]){
p2++;
break;
}else{
if(i == k1 - 1){
//数组1要空了
p2++;
}else if(j == k2 - 1){
//数组2要空了
p1++;
}
}
}
}
}
while(p1 < k1){
res += to_string(t1[p1]);
p1++;
}
while(p2 < k2){
res += to_string(t2[p2]);
p2++;
}
//cout<<endl;
//maxStr = max(res,maxStr);
maxStr = maxStr > res ? maxStr : res;
//cout<<res<<endl;
//清空字符串
res = "";
}
int main(){
//输入整数数组
int t;
while(cin.peek() != '\n'){
scanf("%d",&t);
nums1.push_back(t);
}
//删掉输入流中的回车符
cin.ignore(1,'\n');
while(cin.peek() != '\n'){
scanf("%d",&t);
nums2.push_back(t);
}
//删掉输入流中的回车符
cin.ignore(1,'\n');
//输入位数
scanf("%d",&k);
//-------------------------------
n1 = nums1.size();//数组1长度
n2 = nums2.size();//数组2长度
//分治
for(int i = 0;i <= k;i++){
if(i > n1){
break;
}
//printf("i=%d\n",i);
if(k - i <= n2){
//找各个情况下的
divide(i,k - i);
}
}
//结果转换为数组
string s;
for(int i = 0;i < k;i++){
//存在二义性，应该先将各个字符转换为字符串
//result.push_back(stoi(maxStr[i]));
//防止maxStr[i]中含有非数字的字符
if(isdigit(maxStr[i])){
s = string(1,maxStr[i]);
result.push_back(stoi(s));
}
}
//输出结果
for(int i = 0;i < k;i++){
printf("%d",result[i]);
}
return 0;
} 解题思路：要求的最大数的位数一定，需要从两个数组中选数，所以需要用分治考虑不同分配的情况。在每种分治的情况下，可以用改良后的单调栈来选取每个数组中要选取的数，要尽可能先选取更大的数（栈顶的元素要更小）且要保证单调栈中最终的元素个数。
注意：
? ? ? ? 字符串->整型：to_string(string str);
? ? ? ? ? ? ? ? to_string()不能将字符转换为整型，如遇字符，需要先用string(1,char c);将字符转换为字符串。
? ? ? ? 整型->字符串：stoi(int i);
????????
? ? ? ? 思路清楚最重要！！！