[LintCode] Delete Digits [Greedy]

張漢慶發(fā)布于2019-08-14 15:21 / 1887人閱讀

摘要：題意為取刪去個字符后最小的值，仍以返回。所以無論刪除個元素之后的元素放入順序如何，此時棧內(nèi)元素從底到頂?shù)呐帕幸欢ㄊ菨M足條件的最小值。這種情況下，就要從堆棧頂部刪除剩下的兩個元素和然后，將棧內(nèi)的元素放入，并將頂部的全部去掉，然后以返回。

Problem

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Example

Given an integer A = "178542", k = 4

return a string "12"

Note

題意為取String A刪去k個字符后最小的值，仍以String返回。
使用Greedy的解法如下：
首先通過用字符與"0"相減的結(jié)果int cur進(jìn)行數(shù)值大小的比較。然后遍歷整個字符串，將較小的元素替換棧內(nèi)較大元素并放在棧底，形成一個從底部到頂端逐漸增大的堆棧。例如0812743456（不考慮刪除元素個數(shù)k），堆棧的排列從下到上就變成123456了。又例如087123654，k = 2,那么放入堆棧后就變成0123654。
那么，現(xiàn)在就有兩種情況：刪掉的元素數(shù)目小于或等于k。
如果在for循環(huán)中正好刪除了k個元素，這k個元素一定是從原字符串A的高位（棧底）開始刪除的。所以無論刪除k個元素之后的元素放入順序如何，此時棧內(nèi)元素從底到頂?shù)呐帕幸欢ㄊ菨M足條件的最小值。
如果在for循環(huán)刪除的元素少于k個，一定是這樣的情況：081234567, k = 3, 在for循環(huán)結(jié)束的時候只刪除了元素8，因為剩下的元素是一個完全上升序列01234567。這種情況下，就要從堆棧頂部刪除剩下的兩個元素6和7.
然后，將棧內(nèi)的元素放入StringBuilder，并將StringBuilder頂部的"0"全部去掉，然后以.toString()返回String。

Solution

public class Solution {
    public String DeleteDigits(String A, int k) {
        if (A == null || A.length() < k) return null;
        Stack stack = new Stack();
        int deleted = 0;
        for (int i = 0; i < A.length(); i++) {
            int cur = A.charAt(i) - "0";
            while (!stack.isEmpty() && stack.peek() > cur && deleted < k) {
                stack.pop();
                deleted++;
            }
            stack.push(cur);
        }
        while (deleted++ < k) stack.pop();
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.insert(0, stack.pop());
        while (sb.charAt(0) == "0") sb.deleteCharAt(0);
        return sb.toString();
    }
}