去除k个元素后的最大值/最小值——类单调栈

本文主要是介绍去除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. 一招吃遍力扣四道题，妈妈再也不用担心我被套路啦～

这篇关于去除k个元素后的最大值/最小值——类单调栈的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！