本文共 1223 字,大约阅读时间需要 4 分钟。
遍历每个数字,如果数字小于相邻数字则丢弃相邻数字。
如果输入数字有序,为了必须丢弃k个,要丢弃末尾k个返回。时间复杂度:虽然内层还有一个 while 循环,但是由于每个数字最多仅会入栈出栈一次,因此时间复杂度仍然为 O(N),其中 N 为数字长度。
空间复杂度:我们使用了额外的栈来存储数字,因此空间复杂度为 O(N),其中 N 为数字长度。class Solution { public String removeKdigits(String num, int k) { if(num==null||num.length()==0) return ""; if(k==0) return num; if(k==num.length()) return "0"; int len=num.length()-k;//最终的长度 Dequestack=new LinkedList<>(); for(int i=0;i c&&k>0){ stack.removeLast(); k--; } stack.addLast(c); } StringBuilder sb=new StringBuilder(len); int flag=0;//去除前导0 for(Character c:stack){ //后面的不需要了,跳出循环 if(len==0) break; //需要数量-1 len--; //是前导0 if(flag==0&&c=='0') continue; //不会是前导0了 if(c!='0') flag=1; //加入结果 sb.append(c.charValue()); } //字符串为空时,返回0 String res=sb.toString(); if(res.length()==0) return "0"; else return res; }}
转载地址:http://tgczk.baihongyu.com/