题目大意：
移掉K位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
- num 的长度小于 10002 且 ≥ k。
- num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3 输出: "1219" 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1 输出: "200" 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2 输出: "0" 解释: 从原数字移除所有的数字，剩余为空就是0。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=402
解题思路分析：
这道题目需要思考的点很多。试想要想得到剩下的数字最小，也就是说我们要删除掉高位上的较大数字。这是本题思想的核心部分，那么哪些数字是高位上较大的数字呢？比如数字213，虽然3是其中最大的数字，如果将它删除后可以得到数字21，但是显然删除2后得到的数字13更小。
逻辑上，我们从高位向低位循环，如果当前数字大于等于前一位上的数字，这时我们要是删除前一位的话，当前数字顶替到高位后只能使得数字变得更大（或者不变），因此此时我们将当前数字保留即可。反之如果当前数字小于前一位上的数字，说明在高位上存在较大的数，删除高位后，当前较小的数字即可顶替到它的位置，这样也就起到减少原数字的作用，同时，由于我们删除了一位数，此时的k值应该相应减一。当k为0时，说明我们无须再删除数字，剩下的所有数字都应该被保留。
解题时，我们使用Stack来保存剩下的数字，我们用当前位上的数字与Stack栈顶的数字进行比较，如果当前数字小于栈顶数字，则将栈顶数字pop出栈，同时k值减一。直到当前数字大于等于栈顶数字为止，然后将当前数字push入栈，并循环至下一个数字。这里需要注意一点，如果当前数字是0，并且栈中元素个数为空时，我们不能将该0插入到栈中，这个0实际上是返回结果的最高位，由于题目要求返回结果不能存在前导零，因此此时应该跳过。
循环结束之后，如果k值仍大于0，那么我们需要再删除一些数字。试想经过上述循环中的处理，当前Stack中的数字应该是一个非递减排序的列表（栈顶元素最大），我们只要从栈顶开始pop出栈k个元素即可。
最后我们再将Stack中剩下的元素拼接称为字符串返回。另外需要注意两点，首先，由于Stack中的元素是倒序出栈，因此，我们需要将其反向拼接才能组成正确的结果。另外，如果此时Stack的元素个数为0，直接返回0即可。
实现代码：
public String removeKdigits(String num, int k) {
// 为了提高效率，先将字符串转为数组
char[] arr=num.toCharArray();
Stack<Character> s = new Stack<>();
// 循环每个字符
for(int i=0;i<num.length();i++){
// 如果栈元素个数大于0并且k大于0，并且当前元素大于栈顶元素
while(s.size()>0&&k>0&&arr[i]<s.peek()){
s.pop(); // 栈顶元素pop出栈
k--; // k减一
}
// 如果栈内元素个数为0，并且当前数字是0，跳过（前导零）
if(s.size()==0&&arr[i]=='0') continue;
// 将当前数字入栈
s.push(arr[i]);
}
// 如果k仍大于0
while(k>0&&s.size()>0){
// 从栈顶pop出k个最大数
s.pop();
k--;
}
// 如果栈内元素个数为空，返回0
if(s.size()==0) return "0";
// 将栈内元素组成字符串返回
StringBuilder sb=new StringBuilder();
while(s.size()>0) sb.append(s.pop());
sb.reverse();
return sb.toString();
} 本题解法执行时间为6ms。
Runtime: 6 ms, faster than 66.03% of Java online submissions for Remove K Digits.
Memory Usage: 40.2 MB, less than 9.09% of Java online submissions for Remove K Digits.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-402-remove-k-digits-解题思路分析/