贪心算法的几道经典的题目，体会里面的思想和精髓
贪心可以看做是特殊的动态规划问题，可以进一步的降低动态规划的时间复杂度，利用贪心原则从内向外依次的求出当前子问题的最优解，不会从整体考虑问题，而是想要达到局部最优，只有内部的子问题求得最优解，才能继续解决包含子问题的下一个子问题，前一个子问题的最优解会是下一个子问题最优解的一部分。贪心算法解决相应问题时会比较简单和高效，省去了寻找全局最优解很多不必要的穷举操作，由于贪心算法问题并没有固定的贪心策略，所以唯一的难点就是找到带求解问题的贪心策略，但毕竟熟能生巧嘛，算法的基本思想总是固定不变的。

基本步骤如下：

1. 将问题分解为若干个子问题
2. 找出适合的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优解

还可以解决哪些问题：
区间的调度问题：(InTERVAL Scheduling)
给很多的[start,end]区间是，设计一个算法，算出这些区间中最多有多少个互不相交的区间
实际的一些应用（预定会议）：今天有好几个活动，每个活动都可以用区间[start,end]来表示开始和结束时间，请问最多能够参加几个活动的问题，这个问题就是在求这些时间区间的最大不相交子集的问题
采用贪心的思路，正确的步骤如下：

1. 从区间集合intvs中选择一个区间x，这个x是在当前所有区间中结束最早的（end最小）：可以把每个区间的end按升值排序
2. 把所有与x区间相交的区间从区间集合intvs中删除
3. 重复1和2的步骤，直到intvs为空为止，之前选出的那些x就是最大不相交子集

下面的这张图用于辅助理解：


相关实现的代码如下：

public int intervalSchedule(int[] [] intvs){
    if (intvs.length==0) return 0;
    // 按end升序排序
    Arrays.sort(intvs,new Comparator<int[]>(){
        return a[1] - b[1];
    }
})
//至少有一个区间不相交
int count =1;
//排序后，第一个区间就是x
int x_end = intvs[0][1];
for (int[] interval:intvs) {
        int start = interval[0];
        if (start >= x_end) {
            // 找到下一个选择的区间了
            count++;
            x_end = interval[1];
        }
    }
    return count;
}

这里理解清楚了就可以看看无重叠区间这一道题目

主要的几道题目：（有几道暂时没有整理，有空或者后面的时候再做）

1. leetcoad455-分发饼干
2. leetcoad376-摆动序列
3. leetcoad134-加油站
4. leetcoad860-柠檬水找零
5. LeetCode 55跳跃游戏
6. leetcoad322-零钱兑换
7. leetcoad11-盛最多水的游戏
8. LeetCode 452-用最少数量的箭引爆气球
9. leetcoad435.无重叠区间
10. LeetCode 402移掉 K 位数字
11. LeetCode 763划分字母区间
12. LeetCode 56合并区间

本质上是先用暴力解法，然后在优化的基础上想出贪心的解法

leetcoad455-分发饼干（easy）

leetcoad链接：https://leetcode-cn.com/problems/assign-cookies/
这道题之前自己也做过，所以也是需要自己来认真进行整理的一部分，比较典型的一题
解题思路如下：

1. 将孩子们的胃口值小到大的排列
   • 先优先满足胃口小的孩子
2. 将饼干按照从小到大的顺序排列
   • child 代表 g 的下标，即表示有多少孩子的胃口得到满足（思想）
   • cookie 代表 s 的下标，即表示目前有多少饼干被使用了
3. 遍历所有饼干，遍历过后，饼干只有两种状态（要么有了归属，要么被丢弃）
   • 要么找到了需要这个饼干的孩子
   • 要么剩下的孩子中，胃口值最低的孩子都大于这个饼干的值，那么这个饼干没有人要
     • 比如一块饼干在当前不能满足孩子的需求，那么这块饼干在剩下的饼干中就更不能满足相应的需求，这块饼干就失去了分发的意义了
     • 查看下一个饼干能否找到需要的孩子（查看下一个饼干的状态）
4. 返回孩子的数量

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()     #对g进行排序
        s.sort()     #对s进行排序
        n, m = len(g), len(s)   #记录g 和 s的数组长度
        i = j = count = 0       #设定变量的下标的初始条件为0

        while i < n and j < m:
            while j < m and g[i] > s[j]:
                j += 1
            if j < m:
                count += 1    #cout = count + 1
            i += 1            #i = i +1
            j += 1            #j = j +1
        
        return count
a = Solution()

采用吴师兄的思路来解答：

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        # 1、将孩子们的胃口值按照从小到大的顺序排列
        # 优先满足胃口小的孩子
        g.sort()
        # 2、将饼干按照从小到大的顺序排列
        s.sort()
        # child 代表 g 的下标，即表示有多少孩子的胃口得到满足
        child = 0
        # cookie 代表 s 的下标，即表示目前有多少饼干被使用了
        cookie = 0
        # 遍历所有的饼干
        # 遍历过后，饼干只有两种状态
        # 1、要么找到了需要这个饼干的孩子
        # 2、要么剩下的孩子中，胃口值最低的孩子都大于这个饼干的值，那么这个饼干没人要
        while cookie < len(s) and child < len(g):
            # 孩子的胃口得到了满足
            if s[cookie] >= g[child]:
                # 得到满足的孩子数量加 1
                child += 1
                
            # 查看下一个饼干能否找到需要的孩子
            cookie +=1
        # 最后返回孩子数量
        return child

leetcoad376-摆动序列(middle)

leetcoad链接：https://leetcode-cn.com/problems/wiggle-subsequence/
视频链接：https://www.algomooc.com/1341.html
题目描述：
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素****或者含两个不等元素的序列也视作摆动序列。
1. 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
2. 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
实例一：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

实例二：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

首先就是需要理解题意：
这里有几个关键词：子序列，摆动序列（两数之差交替摆动：有上升摆动序列、下降摆动序列），可以删除，最长
解题步骤如下：

1. 在原数组中挑选出一些元素组成子序列，维持一个摆动序列的状态
2. 对于每一个元素都会处理三种状态
   1. 当前元素没有加入摆动序列
   2. 当前元素处理上升状态
   3. 当前元素处于下降状态
3. 遍历元素，选出三种状态构成摆动序列
   以下用几组图片辅助理解：
   
   
   
   
   这题按照思路还是用的贪心的思想，只有真正的V型（波峰或者波谷位置）翻转才会增加摆动序列的长度。。但是很显然也是可以用动态规划的思路来解题的，不过这里由于时间原因，也只能先搞懂其中的一种方法（把其中的一种方式弄懂已经很花费精力了，太难了）

from typing import List
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n=len(nums)
        # 定义三种状态：0，1 ，2分别表示初始，上升以及下降状态
        beginState,upState,downState=0,1,2

        # 如果数组的长度只有1，直接返回即可
        if len(nums) <2:
            return len(nums)
        length=1

        # 从初始状态开始
        state=beginState
        for i in range(1,len(nums)):
            # 1. 位于初始状态
            if state ==beginState:
                # 如果此时nums[i] > nums[i-1],代表着现在处于上升过程
                if nums[i] > nums[i-1]:
                    state=upState
                    length+=1
                # 如果nums[i] <nums[i-1],代表着现在处于下降过程
                elif nums[i]<nums[i-1]:
                    state=downState
                    length+=1

            # 2. 位于上升状态
            elif state==upState:
                # 只有nums[i]<nums[i-1]时，此时nums[i-2] ,nums[i-1],nums[i]这三者形成了一个波峰
                # 状态开始翻转，由之前的上升状态变为下降状态，同时摆动序列的长度+1
                if nums[i] < nums[i-1]:
                    state=downState
                    length+=1
            
            # 3. 位于下降状态
            elif state==downState:
                # 只有nums[i]>nums[i-1]时，此时nums[i-2] ,nums[i-1],nums[i]这三者形成了一个波谷
                # 状态开始翻转，由之前的下降状态变为上升状态，同时摆动序列的长度+1
                if nums[i] > nums[i-1]:
                    state=upState
                    length+=1
        return length

if __name__ == '__main__':
    nums = [1,17,5,10,13,15,10,5,16,8]
    res=Solution().wiggleMaxLength(nums)
    print(res)

这里还有一篇参考资料值得借鉴，主要是写的十分的详细
https://leetcode.cn/problems/wiggle-subsequence/solution/python3-yi-tu-sheng-qian-yan-by-v12de-ao-72b1/

from typing import List
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        # 用trend表示摆动序列最后的趋势：0代表未知（即初始状态），-1代表下降，1代表上升
        res,trend=1,0
        for i in range(1,len(nums)):
            # 如果发现当前的数比之前的数大，并且当前是初始状态或下降状态
            if nums[i]>nums[i-1] and trend<=0:
                # 长度+1，同时状态转变为上升状态
                res+=1
                trend=1
            # 如果发现当前的数比之前的数小，并且当前要么是初始或上升状态
            elif nums[i]<nums[i-1] and trend>=0:
                # 长度+1，同时状态转变为下降状态
                res+=1
                trend=-1
        return res


if __name__ == '__main__':
    nums = [1,17,5,10,13,15,10,5,16,8]
    res=Solution().wiggleMaxLength(nums)
    print(res)

leetcoad134-加油站(middle)

leetcoad链接：https://leetcode-cn.com/problems/gas-station/
视频链接：https://www.algomooc.com/1737.html
比较有循序渐进的解题思路，值得借鉴：https://leetcode-cn.com/problems/gas-station/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--30/
题目解读：每个节点表示添加的油量，每条边表示消耗的油量，题目的意思是问问我们从哪个节点出发还可以回到该节点，只能用顺时针的方式。
后面可以尝试运用多种解法来解题，开阔自己的思路，必须要从暴力解法开始，一步步的进行相应的优化过程才是一个良性的过程
解法一：暴力解法
考虑从第 0 个点出发，能否回到第 0 个点。
考虑从第 1 个点出发，能否回到第 1 个点。
…
考虑从第 n 个点出发，能否回到第 n 个点。

#此种解法超时，不能通过
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #获取加油站的数量
        n = len(gas)
        for i in range(n):
            j = i
            #初始化：最开始剩余的油量就第一个点的油量
            remainGas = gas[i]
            #当前剩余的油能否达到下一个点
            while (remainGas-cost[j]) >=0:
                remainGas =remainGas - cost[j] +gas[(j +1)%n]
                j = (j +1)%n
                #判断j是否回到了i
                if j==i:
                    return i
        return -1

解法二：贪心算法
此道题的要点如下：
step1:统计所有加油站汽油的总量能否支持汽车跑完全部的路程,，如果不能则无论从哪里出发都不可能绕环路行驶一周
step2：一开始默认的出发点的储油量0，默认出发位置的索引在0 ，依次遍历每个加油站，在遍历的过程中执行跳跃操作（这里要理解这里的重复计算的操作，这里是隐含着一定的证明的）
- 如果发现邮箱里面是非负数就可以直接的往前面开
- 如果发现是负数，就直接从新的j号节点开始出发就行
时间复杂度：O(n):两次循环都是单层的
空间复杂度：O(1)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #获取加油站的数量
        n = len(gas)
        #初始默认汽车的储备量为0
        remainGas = 0
        #统计所有加油站汽油的总量能否支持汽车跑完全部的路程
        for i in range(0,n):
            remainGas +=gas[i] - cost[i]
        #如果发现加油站汽油的总量小于所有的路程所要消耗的汽油的总量
        #汽车最终邮箱的汽油为负，无论选择在哪里出发，都不可能绕行环路行驶一周
        if remainGas < 0:
            return -1
        #一开始默认汽车此时储备的汽车油量为 0
        currentGas = 0
        #一开始默认汽车出发位置的索引在0的位置
        i = 0
        #index表示最终选择的出发点，默认为0
        index = 0
        #依次遍历每个加油站，在遍历的过程中，执行相应的跳跃操作
        while i < n:
            #汽车在i号加油站加了gas[i]
            #汽车开到i+1号加油站消耗了cost[i]的汽油
            currentGas +=gas[i] - cost[i]
            if currentGas >=0:
                i +=1

            #如果发现油箱里面的汽油是负数
            #即汽车可以开到 j号加油站，j >= i + 1,那么让汽车继续的往前开
            #否则就直接尝试让汽车从j号加油站重新出发
            else:
                #重新初始化汽车邮箱的油量
                currentGas = 0
                #最终选择的出发点为j号加油站
                index = i+1
                #重新开始出发
                i +=1
        #最终找到了合适的出发点
        return index

leetcoad860-柠檬水找零（easy）

leetcoad链接：https://leetcode-cn.com/problems/lemonade-change/solution/
视频链接:https://www.algomooc.com/935.html
主要用到的贪心算法的思路
由于顾客只可能给你三个面值的钞票，而且我们一开始没有任何钞票，因此我们拥有的钞票面值只可能是 5美元，10 美元和 20美元三种。基于此，我们可以进行如下的分类讨论。

1. 5美元：直接收钱，不需要找零
2. 10美元：如果有5块，直接找零，如果没有找零失败
3. 20美元：我们需要找回 15 美元
   • 如果手中有 10 元 和 5 元钞票，则找零 1 张 10 元和 1 张 5 元的钞票
   • 如果手中只有 5 元的，
     • 数量超过或者等于 3 张，那么找零 3 张 5 元的钞票
     • 没有则找零失败

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        #用来记录5元钞票的数量
        five,ten = 0, 0
        n = len(bills)
        #顾客开始按顺序购买并找零
        for i in range(0,n):
            #如果发现是5元面额
            if bills[i] ==5:
                five +=1
            #如果发现是10元的面额
            #如果手中有5元的钞票，则找零5元
            elif bills[i] ==10:
                if  five >0:
                    five -=1
                    ten +=1
                else:
                    return False
            #如果发现给的是20元的钞票
            else:
                #如果手中有10元和5元的钞票，找零一张10元和一张5元
                if ten >0 and five >0:
                    ten -=1
                    five -=1
                else:
                    #如果手中只有5元的，并且数量>=3张，那么就找零三张5元的钞票
                    if five >=3:
                        five -=3
                    #说明此时手上没有可供找零的方式，返回false
                    else:
                        return False
        return True

LeetCode 55跳跃游戏

略，在另一篇文章里面有单独写这个。

leetcoad435.无重叠区间

题目描述：给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回** 需要移除区间的最小数量，使剩余区间互不重叠** 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
结合开头区间调度的思维，这里用会议预定的思路，将区间（会议）按照右端点进行排序，一定可以找到一个最先结束的会议，这个会议我们首先要加入到最终结果的首个会议（这个会议最先结束就可以给后面争取到更多的时间了，蕴含了贪心的思想），用预定会议的思路只是为了好理解。
自己在写的时候要注意排序算法的注写，如果是自己写的话很可能会超时

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # 将intervals区间按照end的升序排列
        n=len(intervals)
        # for i in range(n):
        #     for j in range(i+1,n):
        #         if intervals[i][1]>=intervals[j][1]:
        #             intervals[i],intervals[j]=intervals[j],intervals[i]
        # 表示要将interval按照end值进行升序排列
        # 此处也采用了匿名函数的形式，这种写法要值得注意
        intervals.sort(key=lambda x:x[1])
        print(intervals)
        # 至少有一个区间不相交
        count=1
        # 排序后，第一个区间就是x
        # x_end表示第一个区间的结尾值
        x_end=intervals[0][1]
        for i in range(1,n):
            # start为从第一个元素开始，区间的开头元素
            start=intervals[i][0]
            # 如果一个区间不想与x的end相交。它的start必须要大于等于x的end（可以区间边界包含）
            if start >= x_end:
                # 找到下一个选择的区间了
                count+=1
                # 同时将当前找到的这个区间赋值给x_end
                x_end=intervals[i][1]
        # 返回最终的结果
        return n-count

leetcoad452-用最少数量的箭引爆气球

题目描述：
有一些球形气球贴在一堵用** XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球**。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
题目分析：
也是采用区间调度的方法，不过还是有一点区别的，需要改一点边界条件

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # 对points数组按照end值进行升序排列
        n=len(points)
        points.sort(key=lambda x:x[1])
        # print(points)
        # 至少有一个区间不相交
        count=1
        # x_end表示第一个区间的结尾值
        x_end=points[0][1]
        # 除开第一数开始往后遍历
        for i in range(1,n):
            # 如果发现后面的数的开头元素是大于前一个数的结尾元素的
            # start表示下一个的左端元素
            start=points[i][0]
            if start > x_end:
                count+=1
                x_end=points[i][1]
        # 循环结束后返回
        return count

leetcoad402-移掉k位数字

题目描述：
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的** k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字**。
实例一：
输入：num = “1432219”, k = 3
输出：”1219”
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

实例二：
输入：num = “10200”, k = 1
输出：”200”
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

思路：（这里地思路很巧妙）

1. 从左到右遍历所有的数字，判断是否需要保留
2. 用栈保留需要遍历的所有的数字
3. 不断地去比较当前遍历元素与栈顶元素比较
4. 移除k位之后，将栈顶地元素挨个弹出，然后进行反转就得到最终的结果

这里面用到了单调栈和贪心的思想（也就只有做题才能体会出来）
问题的关键：我们怎么知道，一个元素是应该保留还是应该丢弃？
前置的数学知识：两相同位数的数字的大小关系取决于第一个不同数的大小
很可能会遗漏的一个点：第一个元素为0的情况（前提是这个数字不全是0）

另一种分析思路：

1. 每次丢弃一次，k-1，当k减到0，我们可以提前终止遍历
2. 当遍历完成，如果k仍大于0（假设最终还剩下x个需要丢弃），我们需要选择删除末尾x个元素（这里判定的思路太重要了）

在上面的思路上来一个逆向的思考的过程：

1. 上面的一直是丢弃，逆向思维就是保留n-k个元素（我们只需要按照上面的方法遍历完成，再截取前n-k个元素）
2. 通过思路的分析来选择数据结构：我们需要保留和丢弃相邻的元素，可以使用栈这种再一端进行添加和删除的数据结构
   
   这里附上代码

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # 初始化栈，用来存储需要保存的数字
        stack=[]
        # 从左到右遍历字符串 num
        for c in num:
            # 如果此时
            # 1、栈不为空
            # 2、栈顶元素大于此时遍历的字符
            # 3、还没有删除足够多的数字，即 k > 0
            # 那么这个时候需要把栈顶元素弹出
            # 这里在移除元素的时候就用到了贪心的思想
            while k and stack and stack[-1] >c:
                stack.pop()
                k-=1
            # 把符合要求的字符放入到栈中
            stack.append(c)
            # print(stack)
        return ''.join(stack[:len(stack) - k]).lstrip('0') or '0'

这里有几行重要的代码，值得自己思考：
这里要补充单调栈的知识点：
在栈的基础上，从栈顶到栈底的元素是严格的递增或递减的
具体的进栈过程：

1. 对于单调递增栈，若当前进栈元素为 e，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直接遇到一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中。
2. 对于单调递减栈，则每次弹出的是大于 e 或者等于 e 的元素。

举例子说明：3，4，2，6，4，5，2，3（按照单调递增栈的思路）

还有最后的一行代码
这里举两个调试的例子：num=’9’ ,k=1,按道理应该要返回’0’，因为移除之后，数字就为空了
num=’10’,k=1,按道理要返回’0’，如果你不是按上面写的，而是在上面写上一个判断条件：

if k>=len(num):
    return '0'

虽然考虑到了将全部元素移除后为空的情况，但是却不能考虑到有些’0’是因为去移除一部分本身还剩下的是元素0（不是空，但是元素是’0’）,所有返回的结果也是有问题
综上所述，最后一个返回的条件要兼顾以下的几种情况：

1. 移除一些元素之后，前导为0的，去除前导之后能够返回
2. 移除元素之后，本身已经为空了，需要返回’0’
3. 移除元素之后，还剩的元素本身为’0’,也要返回’0’

当把这个题目做完了之后，再反思看其他人的一些优秀题解，也有新的启发（按说这些解法都是相通的，所以还是要动脑筋才能看懂，要花费很多的精力呀，能看懂是一方面，会写又是另一个方面，这里面的门道还真多）：
比如这里的一篇题解：https://leetcode.cn/problems/remove-k-digits/solution/wei-tu-jie-dan-diao-zhan-dai-ma-jing-jian-402-yi-d/

1. 从左至右扫描，当前扫描的数还不确定要不要删除，入栈缓存
2. 123531这样高位递增的数，肯定是想着尽量删除低位的部分，保留高位的部分
3. 432135这种高位递减的数，会想到让高位变小
4. 如果当前遍历的数比栈顶大，符合递增，是满意的，让它入栈。
5. 如果当前遍历的数比栈顶小，栈顶立刻出栈，不管后面有没有更大的，为什么？

这样做的原因：栈顶数属于高位，删掉它，小的顶上，高位变小好于低位变小
但是对于特殊的情况的处理，比如0432219，0一开始就被遇到，它是最小的，最后肯定会被留在里面
这里的处理方式有两种：
事先处理：加入一个判断，当c==0的时候，由于我们写的是入栈的条件，所以就被改写成：

if c!=0 and len(stack)!=0:
    stack.append(c)

事后处理：就是题目中的写法，用strip()函数来去除字符串前面的0
还有一种情况也需要处理：遍历结束时，有可能没有删除够k个字符，继续循环出栈，删除低位
如果删除够了：

1. 栈变空：什么也不剩了，直接返回”0”
2. 栈中还有元素，将栈中剩下的字符，转成字符串返回

什么时候用单调栈？：需要给当前的元素，找右边/左边第一个比他大/小的位置
总结：

1. 单调递增栈，利用波谷剔除栈中的波峰，留下波谷；
2. 单调递减栈，利用波峰剔除栈中的波谷，留下波峰。

这个时候再次回到本题中：
本题就是维护了一个单调递增栈，找右边第一个比它小的数（右侧的第一个波谷）
遇到波谷，就剔除单调栈中的波峰，维持单增（留下了波谷就是保持了单增，剔除的栈中的字符就是删除的字符）

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if len(num)==k:
            return "0"
        stack=[]
        # 遍历字符串
        for c in num:
            # 只要k>0并且当前的c比栈顶的小，则栈顶出栈，k值-1
            while k >0 and len(stack)>0 and stack[-1] >c:
                stack.pop()
                k-=1
            # 如果当前的字符不是0，或栈非空（避免0入空栈），入栈
            if c!='0' or len(stack)!=0:
                stack.append(c)
        # 如果还没有删除够，要从stack继续删除，直到k=0
        while k>0 and len(stack)!=0:
            stack.pop()
            k-=1
        # 如果栈空了，返回'0',如果栈非空，转成字符串返回
        if len(stack)==0:
            return '0'
        return ''.join(stack[:len(stack)])