欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-22 16:38:39
文章目录前言一、题目描述1. 问题陈述2. 解题思路二、从单个数组中获得最大数三、合并使结果数最大四、完整代码(python版)总结前言这篇博文主要参考leetcode中的一篇题解一招吃遍力扣四道题,题解的作者详细总结了针对该类型题目的思路,以三道题目为例,讲解了如何用单调栈求解此类题目。Leetcode321题是其中的一道,属于困难题目,它的基本思想仍然是单调栈,不过在此基础上还需要一些后续步骤,才能求解最终答案。原题解已经写的比较清楚,这里就是自己的一个小回顾。大家可以看原题解,有配图好理解~...


前言

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

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


一、题目描述

1. 问题陈述

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

2. 解题思路

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

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


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

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

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

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

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

解决这个问题前,我们先来看一个更基础的问题402.移掉K位数
拼接最大数——单调栈的使用


这种问题,上来就遍历hhhh

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

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

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

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

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

但当我们在遍历过程中“可弹出次数”没有用完时,最后得到的结果就长了,这时直接截取前 l e n ( n u m ) − K len(num)-K 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 A A中找到长度是 i i i的最大数,那不就是移除 A A A m − i m-i mi个数使剩下数最大嘛。由于要使剩下数最大,我们需要构建一个单调减栈,其他步骤和上面完全一样!

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

三、合并使结果数最大

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

合并规则:

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 ∗ ( k 2 + m + n ) ) O(k*(k^2+m+n)) O(k(k2+m+n))
空间复杂度: O ( m a x ( m , n , k ) ) O(max(m,n,k)) O(max(m,n,k))


总结

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

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