字典序列刪除 · ttttt

# 字典序列刪除 # 一招吃遍力扣四道題，媽媽再也不用擔心我被套路啦～我花了幾天時間，從力扣中精選了四道相同思想的題目，來幫助大家解套，如果覺得文章對你有用，記得點贊分享，讓我看到你的認可，有動力繼續做下去。這就是接下來要給大家講的四個題，其中 1081 和 316 題只是換了說法而已。 - [316. 去除重復字母](https://leetcode-cn.com/problems/remove-duplicate-letters/)(困難) - [321. 拼接最大數](https://leetcode-cn.com/problems/create-maximum-number/)(困難) - [402. 移掉 K 位數字](https://leetcode-cn.com/problems/remove-k-digits/)(中等) - [1081. 不同字符的最小子序列](https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/)（中等） ## 402. 移掉 K 位數字（中等）我們從一個簡單的問題入手，識別一下這種題的基本形式和套路，為之后的三道題打基礎。 ### 題目描述 ``` <pre class="calibre18">``` 給定一個以字符串表示的非負整數 num，移除這個數中的 k 位數字，使得剩下的數字最小。注意: num 的長度小于 10002 且 ≥ k。 num 不會包含任何前導零。示例 1 : 輸入: num = "1432219", k = 3 輸出: "1219" 解釋: 移除掉三個數字 4, 3, 和 2 形成一個新的最小的數字 1219。示例 2 : 輸入: num = "10200", k = 1 輸出: "200" 解釋: 移掉首位的 1 剩下的數字為 200. 注意輸出不能有任何前導零。示例 3 : 輸入: num = "10", k = 2 輸出: "0" 解釋: 從原數字移除所有的數字，剩余為空就是 0。 ``` ``` ### 前置知識 - 數學 ### 思路這道題讓我們從一個字符串數字中刪除 k 個數字，使得剩下的數最小。也就說，我們要保持原來的數字的相對位置不變。以題目中的 `num = 1432219， k = 3` 為例，我們需要返回一個長度為 4 的字符串，問題在于：我們怎么才能求出這四個位置依次是什么呢？ ![](https://img.kancloud.cn/c1/0d/c10dfc795da7afd8aaeb2e75fd4d9b99_1234x626.jpg) （圖 1）暴力法的話，我們需要枚舉`C_n^(n - k)` 種序列（其中 n 為數字長度），并逐個比較最大。這個時間復雜度是指數級別的，必須進行優化。一個思路是： - 從左到右遍歷 - 對于每一個遍歷到的元素，我們決定是**丟棄**還是**保留** 問題的關鍵是：我們怎么知道，一個元素是應該保留還是丟棄呢？這里有一個前置知識：**對于兩個數 123a456 和 123b456，如果 a > b，那么數字 123a456 大于數字 123b456，否則數字 123a456 小于等于數字 123b456**。也就說，兩個**相同位數**的數字大小關系取決于第一個不同的數的大小。因此我們的思路就是： - 從左到右遍歷 - 對于遍歷到的元素，我們選擇保留。 - 但是我們可以選擇性丟棄前面相鄰的元素。 - 丟棄與否的依據如上面的前置知識中闡述中的方法。以題目中的 `num = 1432219， k = 3` 為例的圖解過程如下： ![](https://img.kancloud.cn/49/a1/49a11aeef217d86033acaa297064f464_1061x1186.jpg) （圖 2）由于沒有左側相鄰元素，因此**沒辦法丟棄**。 ![](https://img.kancloud.cn/c8/64/c864541061c6c25abcf1050ff5c66229_911x1186.jpg) （圖 3）由于 4 比左側相鄰的 1 大。如果選擇丟棄左側的 1，那么會使得剩下的數字更大（開頭的數從 1 變成了 4）。因此我們仍然選擇**不丟棄**。 ![](https://img.kancloud.cn/7b/4e/7b4e55fc93fc35d59895391140e5c680_913x1186.jpg) （圖 4）由于 3 比左側相鄰的 4 小。如果選擇丟棄左側的 4，那么會使得剩下的數字更小（開頭的數從 4 變成了 3）。因此我們選擇**丟棄**。。。。后面的思路類似，我就不繼續分析啦。然而需要注意的是，如果給定的數字是一個單調遞增的數字，那么我們的算法會永遠**選擇不丟棄**。這個題目中要求的，我們要永遠確保**丟棄** k 個矛盾。一個簡單的思路就是： - 每次丟棄一次，k 減去 1。當 k 減到 0 ，我們可以提前終止遍歷。 - 而當遍歷完成，如果 k 仍然大于 0。不妨假設最終還剩下 x 個需要丟棄，那么我們需要選擇刪除末尾 x 個元素。上面的思路可行，但是稍顯復雜。 ![](https://img.kancloud.cn/c6/55/c655f36b495bfd3b6b0cbca7c72044ae_1280x648.jpg)（圖 5）我們需要把思路逆轉過來。剛才我的關注點一直是**丟棄**，題目要求我們丟棄 k 個。反過來說，不就是讓我們保留 n?kn - kn?k 個元素么？其中 n 為數字長度。那么我們只需要按照上面的方法遍歷完成之后，再截取前**n - k**個元素即可。按照上面的思路，我們來選擇數據結構。由于我們需要**保留**和**丟棄相鄰**的元素，因此使用棧這種在一端進行添加和刪除的數據結構是再合適不過了，我們來看下代碼實現。 ### 代碼（Python） ``` <pre class="calibre18">``` 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' ``` ``` ***復雜度分析*** - 時間復雜度：雖然內層還有一個 while 循環，但是由于每個數字最多僅會入棧出棧一次，因此時間復雜度仍然為 O(N)O(N)O(N)，其中 NNN 為數字長度。 - 空間復雜度：我們使用了額外的棧來存儲數字，因此空間復雜度為 O(N)O(N)O(N)，其中 NNN 為數字長度。 > 提示：如果題目改成求刪除 k 個字符之后的最大數，我們只需要將 stack\[-1\] > digit 中的大于號改成小于號即可。 ## 316. 去除重復字母（困難） ### 題目描述 ``` <pre class="calibre18">``` 給你一個僅包含小寫字母的字符串，請你去除字符串中重復的字母，使得每個字母只出現一次。需保證返回結果的字典序最小（要求不能打亂其他字符的相對位置）。示例 1: 輸入: "bcabc" 輸出: "abc" 示例 2: 輸入: "cbacdcbc" 輸出: "acdb" ``` ``` ## 前置知識 - 字典序 - 數學 ### 思路與上面題目不同，這道題沒有一個全局的刪除次數 k。而是對于每一個在字符串 s 中出現的字母 c 都有一個 k 值。這個 k 是 c 出現次數 - 1。沿用上面的知識的話，我們首先要做的就是計算每一個字符的 k，可以用一個字典來描述這種關系，其中 key 為字符 c，value 為其出現的次數。具體算法： - 建立一個字典。其中 key 為字符 c，value 為其出現的剩余次數。 - 從左往右遍歷字符串，每次遍歷到一個字符，其剩余出現次數 - 1. - 對于每一個字符，如果其對應的剩余出現次數大于 1，我們**可以**選擇丟棄（也可以選擇不丟棄），否則不可以丟棄。 - 是否丟棄的標準和上面題目類似。如果棧中相鄰的元素字典序更大，那么我們選擇丟棄相鄰的棧中的元素。還記得上面題目的邊界條件么？如果棧中剩下的元素大于 n?kn - kn?k，我們選擇截取前 n?kn - kn?k 個數字。然而本題中的 k 是分散在各個字符中的，因此這種思路不可行的。不過不必擔心。由于題目是要求只出現一次。我們可以在遍歷的時候簡單地判斷其是否在棧上即可。代碼： ``` <pre class="calibre18">``` 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) ``` ``` ***復雜度分析*** - 時間復雜度：由于判斷當前字符是否在棧上存在需要 O(N)O(N)O(N) 的時間，因此總的時間復雜度就是 O(N2)O(N ^ 2)O(N2)，其中 NNN 為字符串長度。 - 空間復雜度：我們使用了額外的棧來存儲數字，因此空間復雜度為 O(N)O(N)O(N)，其中 NNN 為字符串長度。查詢給定字符是否在一個序列中存在的方法。根本上來說，有兩種可能： - 有序序列：可以二分法，時間復雜度大致是 O(N)O(N)O(N)。 - 無序序列：可以使用遍歷的方式，最壞的情況下時間復雜度為 O(N)O(N)O(N)。我們也可以使用空間換時間的方式，使用 NNN的空間換取 O(1)O(1)O(1)的時間復雜度。由于本題中的 stack 并不是有序的，因此我們的優化點考慮空間換時間。而由于每種字符僅可以出現一次，這里使用 hashset 即可。 ### 代碼（Python） ``` <pre class="calibre18">``` 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) ``` ``` ***復雜度分析*** - 時間復雜度：O(N)O(N)O(N)，其中 NNN 為字符串長度。 - 空間復雜度：我們使用了額外的棧和 hashset，因此空間復雜度為 O(N)O(N)O(N)，其中 NNN 為字符串長度。 > LeetCode 《1081. 不同字符的最小子序列》和本題一樣，不再贅述。 ## 321. 拼接最大數（困難） ### 題目描述 ``` <pre class="calibre18">``` 給定長度分別為 m 和 n 的兩個數組，其元素由 0-9 構成，表示兩個自然數各位上的數字。現在從這兩個數組中選出 k (k <= m + n) 個數字拼接成一個新的數，要求從同一個數組中取出的數字保持其在原數組中的相對順序。求滿足該條件的最大數。結果返回一個表示該最大數的長度為 k 的數組。說明: 請盡可能地優化你算法的時間和空間復雜度。示例 1: 輸入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 輸出: [9, 8, 6, 5, 3] 示例 2: 輸入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 輸出: [6, 7, 6, 0, 4] 示例 3: 輸入: nums1 = [3, 9] nums2 = [8, 9] k = 3 輸出: [9, 8, 9] ``` ``` ### 前置知識 - 分治 - 數學 ### 思路和第一道題類似，只不不過這一次是兩個**數組**，而不是一個，并且是求最大數。最大最小是無關緊要的，關鍵在于是兩個數組，并且要求從兩個數組選取的元素個數加起來一共是 k。然而在一個數組中取 k 個數字，并保持其最小（或者最大），我們已經會了。但是如果問題擴展到兩個，會有什么變化呢？實際上，問題本質并沒有發生變化。假設我們從 nums1 中取了 k1 個，從 num2 中取了 k2 個，其中 k1 + k2 = k。而 k1 和 k2 這兩個子問題我們是會解決的。由于這兩個子問題是相互獨立的，因此我們只需要分別求解，然后將結果合并即可。假如 k1 和 k2 個數字，已經取出來了。那么剩下要做的就是將這個長度分別為 k1 和 k2 的數字，合并成一個長度為 k 的數組合并成一個最大的數組。以題目的 `nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5` 為例。假如我們從 num1 中取出 1 個數字，那么就要從 nums2 中取出 4 個數字。運用第一題的方法，我們計算出應該取 nums1 的 \[6\]，并取 nums2 的 \[9,5,8,3\]。如何將 \[6\] 和 \[9,5,8,3\]，使得數字盡可能大，并且保持相對位置不變呢？實際上這個過程有點類似`歸并排序`中的**治**，而上面我們分別計算 num1 和 num2 的最大數的過程類似`歸并排序`中的**分**。 ![](https://img.kancloud.cn/23/4e/234e62bdde8d564c63dce9b7783f5956_1586x493.jpg)（圖 6）代碼： > 我們將從 num1 中挑選的 k1 個數組成的數組稱之為 A，將從 num2 中挑選的 k2 個數組成的數組稱之為 B， ``` <pre class="calibre18">``` 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 ``` ``` 這里需要說明一下。在很多編程語言中：**如果 A 和 B 是兩個數組，當前僅當 A 的首個元素字典序大于 B 的首個元素，A > B 返回 true，否則返回 false**。比如： ``` <pre class="calibre18">``` A = [1,2] B = [2] A < B # True A = [1,2] B = [1,2,3] A < B # False ``` ``` 以合并 \[6\] 和 \[9,5,8,3\] 為例，圖解過程如下： ![](https://img.kancloud.cn/fe/0a/fe0aea24c716cce401685d9d55f7515a_1586x974.jpg)（圖 7）具體算法： - 從 nums1 中取 min(i,len(nums1))min(i, len(nums1))min(i,len(nums1)) 個數形成新的數組 A（取的邏輯同第一題），其中 i 等于 0,1,2, ... k。 - 從 nums2 中對應取 min(j,len(nums2))min(j, len(nums2))min(j,len(nums2)) 個數形成新的數組 B（取的邏輯同第一題），其中 j 等于 k - i。 - 將 A 和 B 按照上面的 merge 方法合并 - 上面我們暴力了 k 種組合情況，我們只需要將 k 種情況取出最大值即可。 ### 代碼（Python） ``` <pre class="calibre18">``` 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)) ``` ``` ***復雜度分析*** - 時間復雜度：pick\_max 的時間復雜度為 O(M+N)O(M + N)O(M+N) ，其中 MMM 為 nums1 的長度，NNN 為 nums2 的長度。 merge 的時間復雜度為 O(k)O(k)O(k)，再加上外層遍歷所有的 k 中可能性。因此總的時間復雜度為 O(k2?(M+N))O(k^2 \* (M + N))O(k2?(M+N))。 - 空間復雜度：我們使用了額外的 stack 和 ans 數組，因此空間復雜度為 O(max(M,N,k))O(max(M, N, k))O(max(M,N,k))，其中 MMM 為 nums1 的長度，NNN 為 nums2 的長度。 ## 總結這四道題都是刪除或者保留若干個字符，使得剩下的數字最小（或最大）或者字典序最小（或最大）。而解決問題的前提是要有一定**數學前提**。而基于這個數學前提，我們貪心地刪除棧中相鄰的字符。如果你會了這個套路，那么這四個題目應該都可以輕松解決。 `316. 去除重復字母（困難）`，我們使用 hashmap 代替了數組的遍歷查找，屬于典型的空間換時間方式，可以認識到數據結構的靈活使用是多么的重要。背后的思路是怎么樣的？為什么想到空間換時間的方式，我在文中也進行了詳細的說明，這都是值得大家思考的問題。然而實際上，這些題目中使用的棧也都是空間換時間的思想。大家下次碰到**需要空間換取時間**的場景，是否能夠想到本文給大家介紹的**棧**和**哈希表**呢？ `321. 拼接最大數（困難）`則需要我們能夠對問題進行分解，這絕對不是一件簡單的事情。但是對難以解決的問題進行分解是一種很重要的技能，希望大家能夠通過這道題加深這種**分治**思想的理解。大家可以結合我之前寫過的幾個題解練習一下，它們分別是： - [【簡單易懂】歸并排序（Python）](https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-dan-yi-dong-gui-bing-pai-xu-python-by-azl3979/) - [一文看懂《最大子序列和問題》](https://lucifer.ren/blog/2019/12/11/LSS/) 更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》獲取更多更新鮮的 LeetCode 題解 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)