首页 > 学院 > 开发设计 > 正文

Leetcode 321 - Create Maximum Number(贪心)

2019-11-09 20:56:27
字体:
来源:转载
供稿:网友

题意

给两个数组nums1和nums2,和一个数字k,要求从nums1里面和nums2里面分别找出一些数字,构成一个新的数字,并且新的数字最大。并且nums1里面取的数字和nums2里面取的数字要保持相对顺序不变。

思路

之前做过一道类似的题,只给一个数组,找出k个数,维持相对顺序,求能组成的最大的数。

那么,这道题,其实就是说,在nums1里面找出x个,nums2里面找出y个,x + y == k,求能组成的最大的数。

那么,我们就枚举从nums1里面取i个数(组成最大的数),nums2里面取k - i个数(组成最大的数)。最后归并即可。

需要注意一下几点:

找nums1里面由i个能组成的最大的数的时候,我们维护一个单调增的队列。最后归并的时候,当指针i和j指向的数相同的时候,还要考虑后续元素的影响

代码

class Solution {public: vector<int> get(vector<int> nums1, int k) { vector<int> s; if (!k) return s; int re = nums1.size() - k; for (auto x : nums1) { while (re && s.size() && s.back() < x) {re--; s.pop_back();} s.push_back(x); } s.resize(k); return s; } vector<int> merge(vector<int> v1, vector<int> v2) { vector<int> ans; while (v1.size() || v2.size()) { vector<int> &tv = v1 > v2 ? v1 : v2; ans.push_back(tv[0]); tv.erase(tv.begin()); } return ans; } vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) { vector<int> ans; for (int i = 0; i <= k; i++) { if (i <= nums1.size() && k - i <= nums2.size()) {; vector<int> v1 = get(nums1, i); vector<int> v2 = get(nums2, k - i); ans = max(ans, merge(v1, v2)); } } return ans; }};
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表