企业官网建设流程全解析

LeetCode 402. 移掉 K 位数字

思路：单调栈（贪心 + 栈）

要让剩下的数字最小，高位数字越小越好。因此从左到右扫描，只要当前数字比栈顶小，且还有移除次数，就弹出栈顶（因为高位更小收益更大）。

核心步骤：

1. 维护一个单调递增栈（栈底到栈顶递增）
2. 遍历每个数字，若 栈顶 > 当前数字 且 k > 0，弹栈并 k–
3. 遍历结束后若 k > 0，说明序列本身是递增的，从末尾删除剩余的 k 个
4. 去掉结果中的前导零，若为空返回 “0”

Java 实现

classSolution{publicStringremoveKdigits(Stringnum,intk){Deque<Character>stack=newArrayDeque<>();for(charc:num.toCharArray()){// 当前数字更小，且还有移除次数，则弹出栈顶while(k>0&&!stack.isEmpty()&&stack.peek()>c){stack.pop();k--;}stack.push(c);}// 若 k 还有剩余（说明原序列单调递增），从末尾移除while(k>0&&!stack.isEmpty()){stack.pop();k--;}// 从栈底到栈顶拼接结果StringBuildersb=newStringBuilder();while(!stack.isEmpty()){sb.append(stack.pollLast());}// 去除前导零inti=0;while(i<sb.length()&&sb.charAt(i)=='0'){i++;}Stringres=sb.substring(i);returnres.isEmpty()?"0":res;}}

复杂度

· 时间：O(n)，每个字符最多入栈、出栈各一次
· 空间：O(n)，栈空间

测试样例

Solutions=newSolution();System.out.println(s.removeKdigits("1432219",3));// "1219"System.out.println(s.removeKdigits("10200",1));// "200"System.out.println(s.removeKdigits("10",2));// "0"System.out.println(s.removeKdigits("9",1));// "0"System.out.println(s.removeKdigits("112",1));// "11"（递增序列，删除末尾）

关键点

易错点 说明
剩余 k 的处理 若输入递增（如 “1234”），栈不会被弹出，需从末尾删除
前导零 如 “10200” 删除 1 后得到 “0200”，需转为 “200”
结果为空的处理 全部删除后返回 “0”
用 ArrayDeque 比 Stack 更快，pollLast 可正向构造结果