leetcode402 移掉K位數字 Java

給定一個以字元串表示的非負整數 num，移除這個數中的 k 位數字，使得剩下的數字最小。

    num 的長度小于 10002 且 ≥ k。

    num 不會包含任何前導零。

示例 1 :

輸入: num = "1432219", k = 3

輸出: "1219"

解釋: 移除掉三個數字 4, 3, 和 2 形成一個新的最小的數字 1219。

解題思路：

使用模拟棧。

周遊num 當K>0 且棧不為空的時候 比較目前字元與棧頂字元

if 目前字元<棧頂字元 将原棧頂字元出棧 目前字元進棧

不滿足上述情況直接入棧  （結果字元串最後長度應該num.length()-k）

結果可能存在001這種，去掉0

用一個index=0

當index< 結果長度 && index對應字元是0 index++;

最後的情況可能：

k=0了 此時得到的是已經可以組成最小數的字元串

k>0 此時隻需要自棧底到num.length()-k的長度

最終結果：

當index==結果字元串最後長度應該num.length()-k 說明最後結果“0”

否則：最終結果是棧内對應的index-num.length()-k元素組成的字元串。

class Solution {
    public String removeKdigits(String num, int k) {
       if(num.length()==0||num.length()<=k)
           return "0";
        char strStack[]=new char[num.length()];
        int newLength=num.length()-k;
        int top=0;
        for(int i=0;i<num.length();i++){
            char c=num.charAt(i);
            while(top>0&&strStack[top-1]>c&&k>0){
                top--;
                k--;
            }
            strStack[top++]=c;
        }
            int index=0;
            while(index<newLength&&strStack[index]=='0')
                index++;
            return index==newLength?"0":new String(strStack,index,newLength-index);
        }
    }