LeetCode 402. 移掉 K 位數(shù)字思路單調(diào)棧貪心 棧要讓剩下的數(shù)字最小高位數(shù)字越小越好。因此從左到右掃描只要當(dāng)前數(shù)字比棧頂小且還有移除次數(shù)就彈出棧頂因?yàn)楦呶桓∈找娓?。核心步驟維護(hù)一個(gè)單調(diào)遞增棧棧底到棧頂遞增遍歷每個(gè)數(shù)字若 棧頂 當(dāng)前數(shù)字 且 k 0彈棧并 k–遍歷結(jié)束后若 k 0說(shuō)明序列本身是遞增的從末尾刪除剩余的 k 個(gè)去掉結(jié)果中的前導(dǎo)零若為空返回 “0”Java 實(shí)現(xiàn)classSolution{publicStringremoveKdigits(Stringnum,intk){DequeCharacterstacknewArrayDeque();for(charc:num.toCharArray()){// 當(dāng)前數(shù)字更小且還有移除次數(shù)則彈出棧頂while(k0!stack.isEmpty()stack.peek()c){stack.pop();k--;}stack.push(c);}// 若 k 還有剩余說(shuō)明原序列單調(diào)遞增從末尾移除while(k0!stack.isEmpty()){stack.pop();k--;}// 從棧底到棧頂拼接結(jié)果StringBuildersbnewStringBuilder();while(!stack.isEmpty()){sb.append(stack.pollLast());}// 去除前導(dǎo)零inti0;while(isb.length()sb.charAt(i)0){i;}Stringressb.substring(i);returnres.isEmpty()?0:res;}}復(fù)雜度· 時(shí)間O(n)每個(gè)字符最多入棧、出棧各一次· 空間O(n)棧空間測(cè)試樣例SolutionsnewSolution();System.out.println(s.removeKdigits(1432219,3));// 1219System.out.println(s.removeKdigits(10200,1));// 200System.out.println(s.removeKdigits(10,2));// 0System.out.println(s.removeKdigits(9,1));// 0System.out.println(s.removeKdigits(112,1));// 11遞增序列刪除末尾關(guān)鍵點(diǎn)易錯(cuò)點(diǎn) 說(shuō)明剩余 k 的處理 若輸入遞增如 “1234”棧不會(huì)被彈出需從末尾刪除前導(dǎo)零 如 “10200” 刪除 1 后得到 “0200”需轉(zhuǎn)為 “200”結(jié)果為空的處理 全部刪除后返回 “0”用 ArrayDeque 比 Stack 更快pollLast 可正向構(gòu)造結(jié)果