lc.402.移掉k位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

1
2
3

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

示例 2 ：

1
2
3

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

示例 3 ：

1
2
3

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。

提示：

1 <= k <= num.length <= 105 num 仅由若干位数字（0 - 9）组成 除了 0 本身之外，num 不含任何前导零

解题思路

这就是接下来要给大家讲的四个题，其中 1081 和 316 题只是换了说法而已。

  1. 去除重复字母 (困难)
  2. 拼接最大数 (困难)
  3. 移掉 K 位数字 (中等)
  4. 不同字符的最小子序列 （中等）

作者：fe-lucifer 链接：https://leetcode-cn.com/problems/remove-k-digits/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

什么时候用单调栈

可能你会问：什么时候用单调栈？ 需要给当前的元素，找右边/左边第一个比它大/小的位置。 记住这两句话：

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

作者：xiao_ben_zhu 链接：https://leetcode-cn.com/problems/remove-k-digits/solution/wei-tu-jie-dan-diao-zhan-dai-ma-jing-jian-402-yi-d/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

https://pic.leetcode-cn.com/1605446584-nkKQvb-image.png 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char> s;
        string res;
        for(char f:num) {
            while(s.size() && k && s.back() > f) s.pop_back(),--k;
            s.push_back(f);
        }
        while(s.size() && k) k--,s.pop_back();
        int j=0;
        
        while(res.size()==0 && j<s.size() && s[j]=='0') {
            ++j;
        }
        if(j==s.size()) return "0";
        for(int i=j;i<s.size();i++) {
            res+= s[i];
        }
        return res;
    }
};