LeetCode 321. 拼接最大数

Categories:

题目描述
思路分析
1. 解法一：单调栈 + 归并（推荐）
相似题目

题目描述

✅ 321. 拼接最大数

思路分析

解法一：单调栈 + 归并（推荐）

核心思路：

从两个数组分别选出长度为 i 和 k-i 的最大子序列（单调栈）。

将两个子序列按字典序归并得到最大结果。

枚举所有可行的 i，取最大值。

复杂度分析：

时间复杂度：O((m+n) * k)，其中 m、n 为数组长度。

空间复杂度：O(k)，用于构造子序列与合并结果。

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int[] best = new int[k];

        int start = Math.max(0, k - n);
        int end = Math.min(k, m);

        for (int i = start; i <= end; i++) {
            int[] a = maxSubsequence(nums1, i);
            int[] b = maxSubsequence(nums2, k - i);
            int[] merged = merge(a, b);

            if (greater(merged, 0, best, 0)) {
                best = merged;
            }
        }

        return best;
    }

    private int[] maxSubsequence(int[] nums, int k) {
        int[] stack = new int[k];
        int top = 0;
        int drop = nums.length - k;

        for (int num : nums) {
            while (top > 0 && drop > 0 && stack[top - 1] < num) {
                top--;
                drop--;
            }
            if (top < k) {
                stack[top++] = num;
            } else {
                drop--;
            }
        }

        return stack;
    }

    private int[] merge(int[] a, int[] b) {
        int[] res = new int[a.length + b.length];
        int i = 0;
        int j = 0;

        for (int r = 0; r < res.length; r++) {
            if (greater(a, i, b, j)) {
                res[r] = a[i++];
            } else {
                res[r] = b[j++];
            }
        }

        return res;
    }

    private boolean greater(int[] a, int i, int[] b, int j) {
        while (i < a.length && j < b.length && a[i] == b[j]) {
            i++;
            j++;
        }
        if (j == b.length) {
            return true;
        }
        if (i < a.length && a[i] > b[j]) {
            return true;
        }
        return false;
    }
}

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    best := make([]int, k)
    m, n := len(nums1), len(nums2)

    start := max(0, k-n)
    end := min(k, m)

    for i := start; i <= end; i++ {
        a := maxSubsequence(nums1, i)
        b := maxSubsequence(nums2, k-i)
        merged := merge(a, b)

        if greater(merged, 0, best, 0) {
            best = merged
        }
    }

    return best
}

func maxSubsequence(nums []int, k int) []int {
    stack := make([]int, 0, k)
    drop := len(nums) - k

    for _, num := range nums {
        for drop > 0 && len(stack) > 0 && stack[len(stack)-1] < num {
            stack = stack[:len(stack)-1]
            drop--
        }

        if len(stack) < k {
            stack = append(stack, num)
        } else {
            drop--
        }
    }

    return stack
}

func merge(a []int, b []int) []int {
    res := make([]int, 0, len(a)+len(b))
    i, j := 0, 0

    for i < len(a) || j < len(b) {
        if greater(a, i, b, j) {
            res = append(res, a[i])
            i++
        } else {
            res = append(res, b[j])
            j++
        }
    }

    return res
}

func greater(a []int, i int, b []int, j int) bool {
    for i < len(a) && j < len(b) && a[i] == b[j] {
        i++
        j++
    }

    if j == len(b) {
        return true
    }
    if i < len(a) && a[i] > b[j] {
        return true
    }
    return false
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

相似题目

题目	难度	考察点
402. 移掉 K 位数字	中等	单调栈
1673. 找出最具竞争力的子序列	中等	单调栈
316. 去除重复字母	中等	单调栈
1081. 不同字符的最小子序列	中等	单调栈
321. 拼接最大数	困难	贪心、归并

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/17324701