【Python】单调栈之拼接最大数字、字符串

关于去除数字、字母的题型

首先要知道，对于数字，字母，什么情况字典序最大

s[i] < s[i-1]时，s[i-1]应该移除，213中2应该移除，即从左到右，移除逆序第一个数
如何实现以上的移除逆序操作，稍加观察即可发现，该题型是典型的后进先出，即可以用栈来实现，对于这种只保留顺序数字（字符）的栈，我们叫做单调栈

402. 移掉 K 位数字

https://leetcode.cn/problems/remove-k-digits/

思路：
- 当前一个数大于后面一个数时，移除前面这个数
    - 为什么用while，可能出现前面的数都是顺序，最后一个比前面数都小的情况
    - k保证移除k个，stack保证不越界
- 用栈来存放数字
- 保留`len(num) - k`个数，如果k不为0时退出while循环，则表示stack中的数都是顺序，只需要保留remain个数
- 由于lstrip("0")，可能返回`""`的情况，最后做一个短路

最终优化版本：

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'

时间复杂度和空间复杂度分析
- 时间复杂度：O(n)，循环为n，最好为n，最坏为n+k
- 空间复杂度：O(n)，维护了一个单调栈

316. 去除重复字母

1081. 不同字符的最小子序列（两题一模一样）

https://leetcode.cn/problems/remove-duplicate-letters/

https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters/

思路：
- 维护一个dic计数
- stack单调栈
- 遍历s，遍历完该数，计数器--，即计数器表现的是后续还有n个该数
- 遍历核心体：
    - 如果不在栈中则加入栈（确保栈中字符不重复）
    - 栈不为空 & 栈逆序 & 逆序第一个字符计数器 >= 1，逆序第一个字符出栈，当前字符再入栈

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        dic = collections.Counter(s)
        stack = []
        for i in s:
            if i not in stack:
                while stack and stack[-1] > i and dic[stack[-1]] > 0:
                    stack.pop()
                stack.append(i)
            dic[i] -= 1
        return ''.join(stack)

时间复杂度和空间复杂度分析
- 时间复杂度：
    - O(n²)，循环为n，判断字符是否在stack中也是n，即为n²
- 空间复杂度：O(n)，维护了一个单调栈和一个字典

降低时间复杂度解法：

利用集合查询时间复杂度为O(1)的特性，将时间复杂度降为O(n)，（Counter也是循环s进行计数）
空间复杂度依然是O(n)，毕竟2n和3n没什么区别是吧，😁

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        dic = collections.Counter(s)
        container = set()
        stack = []
        for i in s:
            if i not in container:
                while stack and stack[-1] > i and dic[stack[-1]] > 0:
                    container.discard(stack.pop())
                stack.append(i)
                container.add(i)
            dic[i] -= 1
        return ''.join(stack)

321. 拼接最大数

https://leetcode.cn/problems/create-maximum-number/

思路：
- 定义函数获取数组中（保留相对位置）最大数
    - 单调栈，获取逆序最大数
    - 保留k个（注意）
- 定义函数拼接2个数组，获取最大数
- 每个数组可以保留的长度为 0 <= n <= len(nums)，循环，获取2个数组所有的组合，再进行拼接

这里有一些骚操作，比较list的大小，获取max(list([1,2], [2,1]))

class Solution:
    def maxNumber(self, nums1, nums2, k):
        def get_max(num, k):
            stack = []
            drop = len(num) - k
            for i in num:
                while drop and stack and stack[-1] < i:
                    stack.pop()
                    drop -= 1
                stack.append(i)
            return stack[:k]
        
        def merge(A, B):
            res = []
            while A or B:
                bigger = A if A > B else B
                res.append(bigger.pop(0))
            return res

        ans = []
        for i in range(k+1):
            if i <= len(nums1) and k-i <= len(nums2):
                ans.append(merge(get_max(nums1, i), get_max(nums2, k-i)))
        return max(ans)