【LeetCode-402】402.移除k位数字(给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。)
程序员文章站
2022-07-02 10:17:25
...
移除k位数字
给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。
思路:单调栈(贪心+栈)
class Solution {
/*
单调栈的另一个应用,思想为删除靠前的较大的数能够使得最后的数值最小。 构建递增栈,若当前数字小于栈顶元素,则在满足待删减字符数不为0的情况下,栈顶元素出栈,当前数字入栈。
*/
public String removeKdigits(String num, int k) {
//贪心算法+单调栈
if(k >= num.length() || num.length() == 0) {
return "0";
}
//栈顶始终是最大值
Stack<Integer> stack = new Stack<>();
stack.push(num.charAt(0) - '0');
for(int i = 1; i < num.length() ; i++) {
int now = num.charAt(i) - '0';
//可能好几个值都比当前值大,那么我们就在k允许的情况下,去去除它。
while(!stack.isEmpty() && stack.peek() > now && k > 0) {
stack.pop();
k--;
}
//不等于0可以添加进去,
//等于0,栈不为空可以填进去,
if(now != 0 || !stack.isEmpty()) {
stack.push(now);
}
}
//56789这种情况,前面一直比后面小,那就去除栈顶,谁让栈顶最大
while(k > 0) {
k--;
stack.pop();
}
//10,1(当now=0时,满足条件,去掉1,但now为0,且为空。)
if(stack.isEmpty()) {
return "0";
}
StringBuilder res = new StringBuilder();
while(!stack.isEmpty()) {
res.append(stack.pop());
}
//从后往前添加,所以我们要逆序
return res.reverse().toString();
}
}
扩展:相似的题
上一篇: Go 实现热重启的详细介绍
下一篇: Android MVVM组成结构