前言

這篇博文主要參考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 k?i個數字，其中 0 ≤ i ≤ k 0 \le i\le k 0≤i≤k，在遍歷到每一個 i i i時，我們求出此時可以得到的最大數字，最終，我們取獲得的這些最大數字中的最大值，就是最終結果，

現在更詳細地看如何獲得每個 i i i對應的最大數字，可以大概分為幾個步驟：

1. 從 A A A中選取最大的 i i i位數字，同時保證選取數字的順序和原陣列中的一致；
2. 從 B B B中選取最大的 k ? i k-i k?i位數字，同時保證選取數字的順序和原陣列中的一致；
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 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 ? ( 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))

總結

當看到 獲得最大（或小）數/字典序 以及 保持在原陣列中的順序這些字眼時，就要考慮使用單調堆疊求解，堆疊可以保證結果中元素的順序和原順序保持一致，“單調”則可以幫助我們獲得最大/最小的結果！