给两个数组nums1和nums2,和一个数字k,要求从nums1里面和nums2里面分别找出一些数字,构成一个新的数字,并且新的数字最大。并且nums1里面取的数字和nums2里面取的数字要保持相对顺序不变。
之前做过一道类似的题,只给一个数组,找出k个数,维持相对顺序,求能组成的最大的数。
那么,这道题,其实就是说,在nums1里面找出x个,nums2里面找出y个,x + y == k,求能组成的最大的数。
那么,我们就枚举从nums1里面取i个数(组成最大的数),nums2里面取k - i个数(组成最大的数)。最后归并即可。
需要注意一下几点:
找nums1里面由i个能组成的最大的数的时候,我们维护一个单调增的队列。最后归并的时候,当指针i和j指向的数相同的时候,还要考虑后续元素的影响。新闻热点
疑难解答