拼接最大数——单调栈的使用

文章目录

• 前言
• 一、题目描述
• 二、从单个数组中获得最大数
• 三、合并使结果数最大
• 四、完整代码（python版）
• 总结

---

前言

这篇博文主要参考leetcode中的一篇题解一招吃遍力扣四道题，题解的作者详细总结了针对该类型题目的思路，以三道题目为例，讲解了如何用单调栈求解此类题目。Leetcode321题是其中的一道，属于困难题目，它的基本思想仍然是单调栈，不过在此基础上还需要一些后续步骤，才能求解最终答案。

原题解已经写的比较清楚，这里就是自己的一个小回顾。大家可以看原题解，有配图好理解~

---

一、题目描述

1. 问题陈述

2. 解题思路

根据问题描述我们可以知道，需要返回一个指定长度$k$的最大数字，数字中的数来自两个给出的数组$A(len=m),B(len=n)$，并且数字中数的位置要和原数组中保持一致。

我们不知道从$A,B$中分别取几个数来组成最终的结果，因此最直接的解题思路就是，我们遍历可能从$A,B$中选择数字个数的方案，假设从$A$中取$i$个数字，从$B$中取$k-i$个数字，其中$0\le i\le k$。在遍历到每一个$i$时，我们求出此时可以得到的最大数字。最终，我们取获得的这些最大数字中的最大值，就是最终结果。

---

现在更详细地看如何获得每个$i$对应的最大数字，可以大概分为几个步骤：

1. 从$A$中选取最大的$i$位数字，同时保证选取数字的顺序和原数组中的一致；
2. 从$B$中选取最大的$k-i$位数字，同时保证选取数字的顺序和原数组中的一致；
3. 把上面得到的两组数字合并，得到一个最大数字。

其中的1，2步是同样的操作，我们现在就获得了解决问题的核心两步：从一个数组中获得最大数；合并两串数字使结果数最大。

二、从单个数组中获得最大数

这个步骤的求解就用到了单调栈算法 。

解决这个问题前，我们先来看一个更基础的问题402.移掉K位数：

---

这种问题，上来就遍历hhhh

我们遍历$num$中的每个数字，认为这个数字不移除，并把它放到我们的栈里，注意，栈底的数字会是最终结果的最高位数字，栈顶则是最低位；并且一个数字的高位越小 ，数字就越小 。

但放进去之前，我们判断一下要不要移除栈顶的元素。什么情况下弹出呢？我们想要剩下的数字最小，那么现在分情况考虑：

1. 当前元素比栈顶元素大，如果把栈顶弹出了，当前元素就顶替了那个较高数位，这样当前栈顶那一位的数字变大了。这违背了初衷，因此这时不能弹出，直接把当前元素入栈；
2. 当前元素比栈顶元素小，如果把栈顶弹出了，再把当前元素入栈，相当于当前栈顶那一位的数字变小了。正是我们想要的！因此，把栈顶弹出，当前元素入栈。

可以看出，经过上面的操作我们得到的是一个单调增栈。

除了上面的弹出规则外，弹出还受“可移除数字个数”的限制。我们一共能移除$K$个数，不能超不能少，在每一次弹出时都是一次移除，“可移除数字个数”就要减一。当这个值变为0时，我们无法进行移除操作，只能把当前元素直接入栈。

但当我们在遍历过程中“可弹出次数”没有用完时，最后得到的结果就长了，这时直接截取前$len(num)-K$长度的数字就行。

完整代码如下：

class Solution(object):
    def removeKdigits(self, num, k):
        stack = []
        remain = len(num) - k
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)  # 每个元素都要入栈
        return ''.join(stack[:remain]).lstrip('0') or '0'  # 移除多余的0

作者：fe-lucifer

在本题中上面的算法可以直接拿过来用，我们需要在$A$中找到长度是$i$的最大数，那不就是移除$A$中$m-i$个数使剩下数最大嘛。由于要使剩下数最大，我们需要构建一个单调减栈，其他步骤和上面完全一样！

这部分代码先不贴，放在下面的完整代码中。

三、合并使结果数最大

合并两个数组使结果最大，这里需要一个思想，我证明不出来，但是可以用数字试出来，所以我就先记住吧~（大家能证明的话请评论告诉我啊）

合并规则：

1、比较两个子序列的当前元素，如果两个当前元素不同，则选其中较大的元素作为下一个合并的元素；
2、两个当前元素相同时，比较从当前元素开始，两个子序列的剩余部分大小，选择剩余部分大的子序列的当前元素，放到合并结果的当前位置。

这个比较看似比较复杂，但是在python语言中可以直接比较两个列表的大小，不用自己写了：

a = [1,2,3,5]
b = [1,2,3,4]
print(a>b)

output：True

a = [1,2,3,5]
b = [1,3,3,4]
print(a>b)

output：False

a = [1,2,3]
b = [1,2,3,4]
print(a>b)

output：False

---

这里放一个官方题解写的比较函数，返回值>0时，表示subsequence1>subsequence2；返回值<0时，反之：

def compare(self, subsequence1: List[int], index1: int, subsequence2: List[int], index2: int) -> int:
        x, y = len(subsequence1), len(subsequence2)
        while index1 < x and index2 < y:
            difference = subsequence1[index1] - subsequence2[index2]
            if difference != 0:
                return difference
            index1 += 1
            index2 += 1
        
        return (x - index1) - (y - index2)  # 用两序列长度比较大小

这个比较就是从高位开始向下逐位比较，遇到不一样的数字时就可以返回比较结果了；同时长的序列肯定更大。

在解题时，两种方式都可以用，就看哪个简便吧~

四、完整代码（python版）

class Solution:
    def maxNumber(self, nums1, nums2, k):

        def pick_max(nums, k):  # 获得最大剩余数
            stack = [] 
            drop = len(nums) - k
            for num in nums:
                while drop and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            return stack[:k]

        def merge(A, B):   # 合并两子序列
            ans = []
            while A or B:
                bigger = A if A > B else B
                ans.append(bigger.pop(0))
            return ans

        return max(merge(pick_max(nums1, i), pick_max(nums2, k-i)) for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))

作者：fe-lucifer

时间复杂度：$O(k\ast (k^2+m+n))$
空间复杂度：$O(max(m,n,k))$

---

总结

当看到 获得最大（或小）数/字典序 以及 保持在原数组中的顺序这些字眼时，就要考虑使用单调栈求解。栈可以保证结果中元素的顺序和原顺序保持一致，“单调”则可以帮助我们获得最大/最小的结果！

本文地址：https://blog.csdn.net/lijianyi0219/article/details/110489499