1 移掉 K 位數(shù)字

1.1 題目描述

????????題目鏈接：https://leetcode.cn/problems/remove-k-digits/

1.2 思路分析

????????這道題讓我們從一個(gè)字符串?dāng)?shù)字中刪除 k 個(gè)數(shù)字，使得剩下的數(shù)最小。也就說(shuō)，我們要保持原來(lái)的數(shù)字的相對(duì)位置不變。

????????以題目中的 $num=1432219，k=3$ 為例，我們需要返回一個(gè)長(zhǎng)度為 4 的字符串，問(wèn)題在于： 我們?cè)趺床拍芮蟪鲞@四個(gè)位置依次是什么呢？

????????暴力法的話，我們需要枚舉 $C_n^{(}n?k)$ 種序列（其中 $n$ 為數(shù)字長(zhǎng)度），并逐個(gè)比較最大。這個(gè)時(shí)間復(fù)雜度是指數(shù)級(jí)別的，必須進(jìn)行優(yōu)化。

????????一個(gè)思路是：

• 從左到右遍歷
• 對(duì)于每一個(gè)遍歷到的元素，我們決定是丟棄還是保留

????????問(wèn)題的關(guān)鍵是：我們?cè)趺粗?，一個(gè)元素是應(yīng)該保留還是丟棄呢？

????????這里有一個(gè)前置知識(shí)：對(duì)于兩個(gè)數(shù) 123a456 和 123b456，如果 a > b， 那么數(shù)字 123a456 大于 數(shù)字 123b456，否則數(shù)字 123a456 小于等于數(shù)字 123b456。也就說(shuō)，兩個(gè)相同位數(shù)的數(shù)字大小關(guān)系取決于第一個(gè)不同的數(shù)的大小。

????????因此我們的思路就是：

• 從左到右遍歷
• 對(duì)于遍歷到的元素，我們選擇保留。
• 但是我們可以選擇性丟棄前面相鄰的元素。
• 丟棄與否的依據(jù)如上面的前置知識(shí)中闡述中的方法。

????????以題目中的 為例的圖解過(guò)程如下：

????????由于沒(méi)有左側(cè)相鄰元素，因此沒(méi)辦法丟棄。

????????由于 4 比左側(cè)相鄰的 1 大。如果選擇丟棄左側(cè)的 1，那么會(huì)使得剩下的數(shù)字更大（開(kāi)頭的數(shù)從 1 變成了 4）。因此我們?nèi)匀贿x擇不丟棄。

????????由于 3 比左側(cè)相鄰的 4 小。 如果選擇丟棄左側(cè)的 4，那么會(huì)使得剩下的數(shù)字更小（開(kāi)頭的數(shù)從 4 變成了 3）。因此我們選擇丟棄。

????????后面的思路類(lèi)似，這里就不繼續(xù)分析啦。

????????然而需要注意的是，如果給定的數(shù)字是一個(gè)單調(diào)遞增的數(shù)字，那么我們的算法會(huì)永遠(yuǎn)選擇不丟棄。這個(gè)題目中要求的，我們要永遠(yuǎn)確保丟棄 k 個(gè)矛盾。

????????一個(gè)簡(jiǎn)單的思路就是：

• 每次丟棄一次，k 減去 1。當(dāng) k 減到 0 ，我們可以提前終止遍歷。
• 而當(dāng)遍歷完成，如果 k 仍然大于 0。不妨假設(shè)最終還剩下 x 個(gè)需要丟棄，那么我們需要選擇刪除末尾 x 個(gè)元素。

????????上面的思路可行，但是稍顯復(fù)雜。

????????我們需要把思路逆轉(zhuǎn)過(guò)來(lái)。剛才我的關(guān)注點(diǎn)一直是丟棄，題目要求我們丟棄 k 個(gè)。反過(guò)來(lái)說(shuō)，不就是讓我們保留 $n?k$ 個(gè)元素么？其中 n 為數(shù)字長(zhǎng)度。 那么我們只需要按照上面的方法遍歷完成之后，再截取前 $n?k$ 個(gè)元素即可。

????????按照上面的思路，我們來(lái)選擇數(shù)據(jù)結(jié)構(gòu)。由于我們需要保留和丟棄相鄰的元素，因此使用棧這種在一端進(jìn)行添加和刪除的數(shù)據(jù)結(jié)構(gòu)是再合適不過(guò)了，我們來(lái)看下代碼實(shí)現(xiàn)。

class Solution(object):
    def removeKdigits(self, num, k):
        stack = []
        remain = len(num) - k
        for digit in num:               # 構(gòu)建單調(diào)遞增的數(shù)字串
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        return ''.join(stack[:remain]).lstrip('0') or '0'      

????????提示： 如果題目改成求刪除 k 個(gè)字符之后的最大數(shù)，我們只需要將 stack[-1] > digit 中的大于號(hào)改成小于號(hào)即可

2 去除重復(fù)字母

2.1 題目描述

????????題目鏈接：https://leetcode.cn/problems/remove-duplicate-letters/

2.2 思路分析

????????與上面題目不同，這道題沒(méi)有一個(gè)全局的刪除次數(shù) k。而是對(duì)于每一個(gè)在字符串 s 中出現(xiàn)的字母 c 都有一個(gè) k 值。這個(gè) k 是 c 出現(xiàn)次數(shù) - 1。

????????沿用上面的知識(shí)的話，我們首先要做的就是計(jì)算每一個(gè)字符的 k，可以用一個(gè)字典來(lái)描述這種關(guān)系，其中 key 為 字符 c，value 為其出現(xiàn)的次數(shù)。

????????具體算法：

• 建立一個(gè)字典。其中 key 為 字符 c，value 為其出現(xiàn)的剩余次數(shù)。
• 從左往右遍歷字符串，每次遍歷到一個(gè)字符，其剩余出現(xiàn)次數(shù) - 1.
• 對(duì)于每一個(gè)字符，如果其對(duì)應(yīng)的剩余出現(xiàn)次數(shù)大于 1，我們可以選擇丟棄（也可以選擇不丟棄），否則不可以丟棄。
• 是否丟棄的標(biāo)準(zhǔn)和上面題目類(lèi)似。如果棧中相鄰的元素字典序更大，那么我們選擇丟棄相鄰的棧中的元素。

????????還記得上面題目的邊界條件么？如果棧中剩下的元素大于 $n?k$，我們選擇截取前 $n?k$ 個(gè)數(shù)字。然而本題中的 k 是分散在各個(gè)字符中的，因此這種思路不可行的。

????????不過(guò)不必?fù)?dān)心。由于題目是要求只出現(xiàn)一次。我們可以在遍歷的時(shí)候簡(jiǎn)單地判斷其是否在棧上即可。

class Solution:
    def removeDuplicateLetters(self, s) -> int:
        stack = []
        remain_counter = collections.Counter(s)

        for c in s:
            if c not in stack:
                while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:
                    stack.pop()
                stack.append(c)
            remain_counter[c] -= 1
        return ''.join(stack)

????????查詢給定字符是否在一個(gè)序列中存在的方法。根本上來(lái)說(shuō)，有兩種可能：

• 有序序列： 可以二分法，時(shí)間復(fù)雜度大致是 $O(N)$。
• 無(wú)序序列： 可以使用遍歷的方式，最壞的情況下時(shí)間復(fù)雜度為 $O(N)$。我們也可以使用空間換時(shí)間的方式，使用 $N$ 的空間 換取 $O(1)$ 的時(shí)間復(fù)雜度。
  由于本題中的 stack 并不是有序的，因此我們的優(yōu)化點(diǎn)考慮空間換時(shí)間。而由于每種字符僅可以出現(xiàn)一次，這里使用 hashset 即可。

class Solution:
    def removeDuplicateLetters(self, s) -> int:
        stack = []
        seen = set()
        remain_counter = collections.Counter(s)

        for c in s:
            if c not in seen:
                while stack and c < stack[-1] and  remain_counter[stack[-1]] > 0:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
            remain_counter[c] -= 1
        return ''.join(stack)

3 拼接最大數(shù)

3.1 題目描述

????????題目鏈接：https://leetcode.cn/problems/create-maximum-number/

3.2 思路分析

????????和第一道題類(lèi)似，只不不過(guò)這一次是兩個(gè)數(shù)組，而不是一個(gè)，并且是求最大數(shù)。

????????最大最小是無(wú)關(guān)緊要的，關(guān)鍵在于是兩個(gè)數(shù)組，并且要求從兩個(gè)數(shù)組選取的元素個(gè)數(shù)加起來(lái)一共是 k。

????????然而在一個(gè)數(shù)組中取 k 個(gè)數(shù)字，并保持其最?。ɑ蛘咦畲螅?，我們已經(jīng)會(huì)了。但是如果問(wèn)題擴(kuò)展到兩個(gè)，會(huì)有什么變化呢？

????????實(shí)際上，問(wèn)題本質(zhì)并沒(méi)有發(fā)生變化。 假設(shè)我們從 nums1 中取了 k1 個(gè)，從 num2 中取了 k2 個(gè)，其中 k1 + k2 = k。而 k1 和 k2 這 兩個(gè)子問(wèn)題我們是會(huì)解決的。由于這兩個(gè)子問(wèn)題是相互獨(dú)立的，因此我們只需要分別求解，然后將結(jié)果合并即可。

????????假如 k1 和 k2 個(gè)數(shù)字，已經(jīng)取出來(lái)了。那么剩下要做的就是將這個(gè)長(zhǎng)度分別為 k1 和 k2 的數(shù)字，合并成一個(gè)長(zhǎng)度為 k 的數(shù)組合并成一個(gè)最大的數(shù)組。

????????以題目的 nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 為例。 假如我們從 num1 中取出 1 個(gè)數(shù)字，那么就要從 nums2 中取出 4 個(gè)數(shù)字。

????????運(yùn)用第一題的方法，我們計(jì)算出應(yīng)該取 nums1 的 [6]，并取 nums2 的 [9,5,8,3]。 如何將 [6] 和 [9,5,8,3]，使得數(shù)字盡可能大，并且保持相對(duì)位置不變呢？

????????實(shí)際上這個(gè)過(guò)程有點(diǎn)類(lèi)似歸并排序中的治，而上面我們分別計(jì)算 num1 和 num2 的最大數(shù)的過(guò)程類(lèi)似歸并排序中的分。

????????我們將從 num1 中挑選的 k1 個(gè)數(shù)組成的數(shù)組稱之為 A，將從 num2 中挑選的 k2 個(gè)數(shù)組成的數(shù)組稱之為 B，

def merge(A, B):
    ans = []
    while A or B:
        bigger = A if A > B else B
        ans.append(bigger[0])
        bigger.pop(0)
    return ans

????????這里需要說(shuō)明一下。 在很多編程語(yǔ)言中：如果 A 和 B 是兩個(gè)數(shù)組，當(dāng)前僅當(dāng) A 的首個(gè)元素字典序大于 B 的首個(gè)元素，A > B 返回 true，否則返回 false。比如：

A = [1,2]
B = [2]
A < B # True

A = [1,2]
B = [1,2,3]
A < B # False

????????以合并 [6] 和 [9,5,8,3] 為例，圖解過(guò)程如下：

????????具體算法：

• 從 nums1 中 取 $min(i,len(nums1))$個(gè)數(shù)形成新的數(shù)組 A（取的邏輯同第一題），其中 $i$ 等于 0,1,2, … k。
• 從 nums2 中 對(duì)應(yīng)取 $min(j,len(nums2))$ 個(gè)數(shù)形成新的數(shù)組 B（取的邏輯同第一題），其中 $j$ 等于 $k?i$。
• 將 A 和 B 按照上面的 merge 方法合并

????????上面我們暴力了 k 種組合情況，我們只需要將 k 種情況取出最大值即可。

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[0])
                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))

小結(jié)

????????這四道題都是刪除或者保留若干個(gè)字符，使得剩下的數(shù)字最?。ɑ蜃畲螅┗蛘咦值湫蜃钚。ɑ蜃畲螅?。而解決問(wèn)題的前提是要有一定數(shù)學(xué)前提。而基于這個(gè)數(shù)學(xué)前提，我們貪心地刪除棧中相鄰的字符。如果你會(huì)了這個(gè)套路，那么這四個(gè)題目應(yīng)該都可以輕松解決。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-411002.html

參考

• 不用字符的最小子序列：https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/solutions/290204/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-6/

到了這里，關(guān)于數(shù)組（九）-- LC[316]&[321]&[402] 去除重復(fù)字母的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！