参考文献
ref{:target=”_blank”}
相关证明可以使用反证法
C++ 代码
class Solution {
public:
// 枚举从 num1 中选i个,num2中选k-i个,先转化成从num中选择x个数最大
// merge环节,每次选择字典序大的输出一个,原因:在相等的情况下,可以让后面大的数尽快输出,贪心思路
// 时间复杂度 k*(m+n+k^2)
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size(), m = nums2.size();
vector<int> res;
// i 表示选取的个数
for(int i=0; i<=n; ++i){
int j = k-i;
// check j is valid
if(j<0 || j>m)continue;
auto&& a = maxArray(nums1, i);
auto&& b = maxArray(nums2, j);
const auto& c = merge(a, b);
res = max(res, c);
}
return res;
}
vector<int> maxArray(const vector<int>& nums, int len){
// 最大数,即单调递减栈(含相等,因为相等情况不确定后面数的大小,故先保留)
int n = nums.size();
vector<int> stk;
for(int i=0; i<n; ++i){
int now = nums[i];
// stk.size() + n-1-i+1 > len,保证后面还有k个数
while(stk.size() && stk.back() < now && stk.size()+n-i>len)stk.pop_back();
if(stk.size()<len)stk.push_back(now);
}
return stk;
}
vector<int> merge(vector<int>& a, vector<int>& b){
vector<int> res;
while(a.size() && b.size()){
if(b>a){
res.push_back(b[0]);
b.erase(b.begin());
} else {
res.push_back(a[0]);
a.erase(a.begin());
}
}
while(a.size())res.push_back(a[0]), a.erase(a.begin());
while(b.size())res.push_back(b[0]), b.erase(b.begin());
return res;
}
};