刪除k個數(shù)字后的最小值

摘自漫畫算法：

題目：給出一個整數(shù)构诚，從該整數(shù)中去掉k個數(shù)字贵少，要求剩下的數(shù)字形成的新整數(shù)盡可能小，應該如何選取被去掉的數(shù)字滔灶？

其中整數(shù)的長度大于或等于k普碎，給出的整數(shù)大小可以超過long類型的數(shù)字范圍。什么意思录平？

例子：

假設給出一個整數(shù)1593212缀皱，刪去3個數(shù)字动猬，新整數(shù)最小的情況是1212啤斗。

圖1.png

假設給出一個整數(shù)30200，刪去1個數(shù)字赁咙，新整數(shù)最小的情況是200钮莲。

圖2.png

假設給出一個整數(shù)10彼水，刪去2個數(shù)字（注意，這里要求刪去的不是1個數(shù)字凤覆，而是2個），新整數(shù)的最小情況是0叛赚。

圖3.png

解題思路

這個題目要求我們刪去k個數(shù)字稽揭，但我們不妨把問題簡化一下：如果只刪除1個數(shù)字，如何讓新整數(shù)的值最邢啤？

我的第一感覺是優(yōu)先刪除最大的數(shù)字揪胃，但是不對。

注意：數(shù)字的大小固然重要随闪，數(shù)字的位置則更加重要骚勘。大家可以想一想铐伴，一個整數(shù)的最高位哪怕只減少1位俏讹，對數(shù)值的影響也是非常大的。

例子：

給出一個整數(shù)541270936泽疆，要求刪去1個數(shù)字，讓剩下的整數(shù)盡可能小殉疼。

此時捌年，無論刪除哪一個數(shù)字驱证，最后的結果都是從9位整數(shù)變成8位整數(shù)。既然同樣是8位整數(shù)抹锄，顯然應該優(yōu)先把高位的數(shù)字降低逆瑞，這樣對新整數(shù)的值影響最大。

解題思路 — 圖1.png

如何把高位的數(shù)字降低呢伙单？很簡單获高，把原整數(shù)的所有數(shù)字從左到右進行比較，如果發(fā)現(xiàn)某一位數(shù)字大于它右面的數(shù)字吻育，那么在刪除該數(shù)字后念秧，必然會使該數(shù)位的值降低布疼，因為右面比它小的數(shù)字頂替了它的位置。

在上面這個例子中游两，數(shù)字5右側的數(shù)字小于5，所以刪除數(shù)字5贱案，最高位數(shù)字降低成了4。

對于整數(shù)541270936侨糟，刪除一個數(shù)字所能得到的最小值是41270936瘩燥。那么對于41270936秕重，刪除一個數(shù)字的最小值是多少呢厉膀？

解題思路 — 圖2.png

接下來，從剛才的結果1270936中再刪除一個數(shù)字汰具，能得到的最小值又是多少呢菱魔？

由于1<2，2<7，7>0杰妓，所以被刪除的數(shù)字為7。

解題思路 — 圖3.png

這里的每一步都要求得到刪除一個數(shù)字后的最小值巷挥，經(jīng)歷3次验靡，相當于求出了刪除k（k=3）個數(shù)字后的最小值。

像這樣依次求得局部最優(yōu)解胜嗓，最終得到全局最優(yōu)解的思想，叫作貪心算法怔锌。

代碼實現(xiàn)

/**
 * 描述：刪除k個數(shù)字后的最小值問題变过。
 * <p>
 * Create By ZhangBiao
 * 2020/6/8
 */
public class RemoveKDigits {

    /**
     * 刪除整數(shù)的k個數(shù)字，獲取刪除后的最小值
     *
     * @param num 原整數(shù)
     * @param k   刪除數(shù)量
     * @return
     */
    public static String removeKDigits(String num, int k) {
        // 新整數(shù)的最終長度 = 原整數(shù)長度 - k
        int newLength = num.length() - k;
        // 創(chuàng)建一個棧媚狰，用于接收所有的數(shù)字
        char[] stack = new char[num.length()];
        int top = 0;
        for (int i = 0; i < num.length(); i++) {
            // 遍歷當前數(shù)字
            char c = num.charAt(i);
            // 當棧頂數(shù)字大于遍歷到的當前數(shù)字時，棧頂數(shù)字出棧（相當于刪除數(shù)字）
            while (top > 0 && stack[top - 1] > c && k > 0) {
                top -= 1;
                k -= 1;
            }
            // 遍歷到的當前數(shù)字入棧
            stack[top++] = c;
        }
        // 找到棧中第1個非零數(shù)字的位置楞件，依次構建新的字符串
        int offset = 0;
        while (offset < newLength && stack[offset] == '0') {
            offset++;
        }
        return offset == newLength ? "0" : new String(stack, offset, newLength - offset);
    }

    public static void main(String[] args) {
        System.out.println(removeKDigits("1593212", 3));
        System.out.println(removeKDigits("30200", 1));
        System.out.println(removeKDigits("10", 2));
        System.out.println(removeKDigits("541270936", 3));
    }

}

上述代碼非常巧妙地運用了棧的特性裳瘪，在遍歷原整數(shù)的數(shù)字時罪针，讓所有數(shù)字一個一個入棧，當某個數(shù)字需要刪除時泪酱，讓該數(shù)字出棧。最后墓阀，程序把棧中的元素轉化為字符串類型的結果。

下面仍然以整數(shù)541270936经伙，k=3為例：