去除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;

参考链接

  1. 一招吃遍力扣四道题,妈妈再也不用担心我被套路啦~
上一篇:剑指 Offer 09. 用两个栈实现队列


下一篇:【YBTOJ进阶训练指导】出栈序列【模拟】【贪心】