給出一個(gè)字符串A, 表示一個(gè)n位正整數(shù), 刪除其中k位數(shù)字, 使得剩余的數(shù)字仍然按照原來(lái)的順序排列產(chǎn)生一個(gè)新的正整數(shù)。

找到刪除k個(gè)數(shù)字之后的最小正整數(shù)。

N<= 240,k<=N

您在真實(shí)的面試中是否遇到過(guò)這個(gè)題？

Yes

樣例

給出一個(gè)字符串代表的正整數(shù)A和一個(gè)整數(shù)k, 其中A = 178542,k = 4

返回一個(gè)字符串"12"

思路：

我的思路是這樣的。

第一個(gè)數(shù)字在[0,k]之間選一個(gè)，如果選到第一個(gè)數(shù)字，下標(biāo)為i；

第二個(gè)數(shù)字一定從i+1繼續(xù)選。在[i+1，k+1]中選一個(gè)最小的，下標(biāo)為i1；

第三個(gè)數(shù)字一定要在第i1+1后繼續(xù)選。即在[i1+1,k+2]中選一個(gè)最小的；

。。。依此類(lèi)推。

所以在這里，我是要注意的兩個(gè)地方，即如何判斷是否第一次選數(shù)字？

還有一個(gè)如果出現(xiàn)了"012"這樣的情況，它不是我們需要的，而是需要“12”。所以需要判斷如果StringBuffer為空的時(shí)候，0不要加進(jìn)去~以下為我的參考代碼。

public class Solution {
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    public String DeleteDigits(String A, int k) {
        // write your code here
        char[] array=A.toCharArray();
        int length=A.length();
        int step=length-k;
        if(length==k)
            return "0";
        StringBuffer sb=new StringBuffer();
        
        int index=0;
        int j=0;
        
        while(step>0)
        {   
            int flag=1;
            if(step==length-k)//如果是第一次的話，就讓flag=0；
            {
                flag=0;
            }
            char min=58;
            for(int i=index+flag;i<=k+j;i++)
            {   
                
                int temp=array[i]-min;
                if(temp<0)
                {
                    index=i;
                    min=array[i];
                }
            }
            if(sb.length()==0&&array[index]=='0')
            {}
            else{
            sb.append(array[index]);
            }
            step--;
            j++;
        }
        return sb.toString();
    }
}