LeetCode每日一题(321. Create Maximum Number)

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

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]

Constraints:

• m == nums1.length
• n == nums2.length
• 1 <= m, n <= 500
• 0 <= nums1[i], nums2[i] <= 9
• 1 <= k <= m + n

对于任意一个数组 nums， 任何一个固定长度 length 一定对应唯一的一个最大数组， 所以按这个思路往下走， 假设最终要得到的数组长度是 k, 那最终的数组一定是 max_array(nums1, length)与 max_array(nums2, k-length)组合而成的， 所以我们只需要遍历这些情况并且把 max_array1 与 max_array2 合并成最大的长度为 k 的数组就可以了。

impl Solution {
    
    fn max_with_fixed_length(mut nums: Vec<i32>, length: usize) -> Vec<i32> {
    
        let mut stack = Vec::new();
        'outer: while stack.len() + nums.len() > length && nums.len() > 0 {
    
            if stack.is_empty() {
    
                stack.push(nums.remove(0));
                continue;
            }
            let curr = nums.remove(0);
            while let Some(last) = stack.pop() {
    
                if last >= curr {
    
                    stack.push(last);
                    stack.push(curr);
                    continue 'outer;
                }
                if stack.len() + nums.len() + 1 == length {
    
                    break;
                }
            }
            stack.push(curr);
        }
        stack.append(&mut nums);
        if stack.len() > length {
    
            stack = stack[..length].to_vec();
        }
        stack
    }
    fn is_greater(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> bool {
    
        while nums1.len() < nums2.len() {
    
            nums1.push(0);
        }
        while nums1.len() > nums2.len() {
    
            nums2.push(0);
        }
        for (n1, n2) in nums1.into_iter().zip(nums2.into_iter()) {
    
            if n1 == n2 {
    
                continue;
            }
            if n1 > n2 {
    
                return true;
            }
            return false;
        }
        false
    }

    fn merge(nums1: &[i32], nums2: &[i32]) -> Vec<i32> {
    
        let mut res = Vec::new();
        let mut i = 0;
        let mut j = 0;
        while i < nums1.len() && j < nums2.len() {
    
            if nums1[i] == nums2[j] {
    
                if Solution::is_greater(nums1[i + 1..].to_vec(), nums2[j + 1..].to_vec()) {
    
                    res.push(nums1[i]);
                    i += 1;
                    continue;
                }
                res.push(nums2[j]);
                j += 1;
                continue;
            }
            if nums1[i] > nums2[j] {
    
                res.push(nums1[i]);
                i += 1;
                continue;
            }
            res.push(nums2[j]);
            j += 1;
        }
        if i < nums1.len() {
    
            res.append(&mut nums1[i..].to_vec());
        }
        if j < nums2.len() {
    
            res.append(&mut nums2[j..].to_vec());
        }
        res
    }
    pub fn max_number(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> Vec<i32> {
    
        let mut ans = vec![0; k as usize];
        for i in 1..=(k as usize).min(nums1.len()) {
    
            if k as usize - i <= nums2.len() {
    
                let max1 = Solution::max_with_fixed_length(nums1.clone(), i);
                let max2 = Solution::max_with_fixed_length(nums2.clone(), k as usize - i);
                let curr = Solution::merge(&max1, &max2);
                if Solution::is_greater(curr.clone(), ans.clone()) {
    
                    ans = curr;
                }
            }
        }
        ans
    }
}