去除k個元素後的最大值/最小值——類單調棧

這裡将4個類似的題進行彙總，都是通過删除k個元素/重複元素，使得剩下的數組最大/最小，都是采用類單調棧的方法。

單調棧的思路，但是由于每個元素至少一個或者删除個數的限制，棧其實并不是完全單調的。

LC316. 去除重複字母

思路就是遇到一個新字元如果比棧頂小并且在新字元後面還有和棧頂一樣的就把棧頂的字元抛棄了

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

        for ch in s:
            remain_counter[ch] -= 1
            if ch in stack:  # 已經加過的不能再加（貪心：用前面的肯定更小）
                continue
            while stack and ch < stack[-1] and remain_counter[stack[-1]] > 0:
                stack.pop()
            stack.append(ch)
            
        return ''.join(stack)

注意：執行過程中棧不一定是單調，例如

1 3 2 4

，棧就是

1 3 2 4

，2雖然比3小，但不能把3抛棄，因為後面沒有3了。

LC 402. 移掉 K 位數字

思路：從前往後，如果新加入的元素比棧頂小，且K還有剩餘，就加棧頂元素抛棄。

這也有貪心的思想，如果前i個把K次機會用了，總比留着後面用好，是以不會有影響。

代碼實作參考https://leetcode-cn.com/problems/remove-k-digits/comments/667737

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for d in num:
            while stack and k and stack[-1] > d:
                stack.pop()
                k -= 1
            stack.append(d)
        if k > 0:
            stack = stack[:-k]
        return ''.join(stack).lstrip('0') or "0"

注意：執行過程也不一定是單調棧，例如

4 3 4 2 5，K=2

，棧會出現

3 2 5

，可見不是單調的。後面的兩題也是這樣。

LC 1673. 找出最具競争力的子序列

思路：和上題一樣，還不用去前導0。甚至可以直接傳回

return self.removeKnum(nums, len(nums)-k);

保留K個相當于删除

len(nums)-k

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack = []
        remain = len(nums)-k
        for num in nums:
            while stack and num < stack[-1] and remain:
                stack.pop()
                remain -= 1
            stack.append(num)
        return stack[:k]

LC 321. 拼接最大數

題意：選取\(K\)個最大的，改成大于棧頂時出棧；其次是兩次數組，枚舉每種情況，數組A取\(i\)個，那麼數組B就去\(K-i\)個；後面将兩個數組(不一定有序)按隊頭較大者逐個合并。

代碼實作參考https://leetcode-cn.com/problems/create-maximum-number/comments/689718

class Solution:
    def pickKnum(self, nums, k): 
        stack = []
        remove = len(nums)-k;
        for num in nums:
            while stack and num > stack[-1] and remove:
                stack.pop()
                remove -= 1
            stack.append(num)
        return stack[:k]

    def merge(self, A, B):
        nums = []
        while A or B:
            big = A if A>B else B
            nums.append(big[0]);
            big.pop(0)  # A,B會随着bigger的改變而改變
        return nums

    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        ans = [0]*k;
        for i in range(k+1):
            if i <= len(nums1) and k-i <= len(nums2):
                # print(self.pickKnum(nums1, i))
                # print(self.pickKnum(nums2, k-i))
                ans = max(ans, self.merge(self.pickKnum(nums1, i), self.pickKnum(nums2, k-i)))

        return ans;

參考連結

一招吃遍力扣四道題，媽媽再也不用擔心我被套路啦～

個性簽名：時間會解決一切