LeetCode-【单调栈】解题技巧

402. 移掉 K 位数字

正常算法思路：从左到右，找第一个比后面大的字符，删除，去掉前导清零，需要k次扫描，每扫描一次，得到移除一个数字后的解。

贪心+k次扫描：

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if len(num) == k:
            return "0"
        for i in range(k):
            t = ""
            flag = True
            for j in range(0,len(num)-1):
                if num[j]>num[j+1]:
                    t = num[0:j] + num[j+1:]
                    flag = False
                    break
            if flag:
                t = num[:-1]
            num = t
        if int(num) == 0:
            return "0"
        else:
            return num.lstrip("0")

单调栈解法：维护一个不减的单调栈，一旦有栈顶元素大的情况，则表明此栈顶元素需要移除。

贪心+单调栈：

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # 构造单调递增栈
        stack = []

        for i in num:
            # 如果栈顶元素大于接下来的元素,则认为栈顶元素需要移除
            while stack and k and stack[-1] > i:
                stack.pop()
                k-=1
            stack.append(i)
        
        # 因为stack是一个单调栈,但是返回的必须是移除k之后的
        if k>0:
            ret = stack[:-k]
        else:
            ret = stack
        return "".join(ret).lstrip("0") or "0"