LeetCode 402. 移掉 K 位數(shù)字思路單調(diào)棧貪心 棧要讓剩下的數(shù)字最小高位數(shù)字越小越好。因此從左到右掃描只要當(dāng)前數(shù)字比棧頂小且還有移除次數(shù)就彈出棧頂因為高位更小收益更大。核心步驟維護(hù)一個單調(diào)遞增棧棧底到棧頂遞增遍歷每個數(shù)字若 棧頂 當(dāng)前數(shù)字 且 k 0彈棧并 k–遍歷結(jié)束后若 k 0說明序列本身是遞增的從末尾刪除剩余的 k 個去掉結(jié)果中的前導(dǎo)零若為空返回 “0”Java 實現(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 還有剩余說明原序列單調(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ù)雜度· 時間O(n)每個字符最多入棧、出棧各一次· 空間O(n)?？臻g測試樣例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)鍵點易錯點 說明剩余 k 的處理 若輸入遞增如 “1234”棧不會被彈出需從末尾刪除前導(dǎo)零 如 “10200” 刪除 1 后得到 “0200”需轉(zhuǎn)為 “200”結(jié)果為空的處理 全部刪除后返回 “0”用 ArrayDeque 比 Stack 更快pollLast 可正向構(gòu)造結(jié)果