C++でK桁を削除する

文字列として表される非負の整数numがあるとすると、新しい数値が可能な限り最小になるように、数値からk桁を削除する必要があります。したがって、入力が「1432219」のようで、k =3の場合、結果は「1219」になります。

これを解決するには、次の手順に従います-

• スタックstを定義し、空の文字列retを作成します

• n：=numのサイズ

• 0からn–1の範囲のiの場合

  • kがゼロ以外で、スタックが空ではなく、スタックの最上位> num [i]

    • スタックから削除し、kを1減らします

  • stにnum[i]を挿入します

• kが0でない場合、スタックから要素を削除します

• スタックが空ではない間

  • ret：=ret +スタックの最上位、スタックから要素を削除

• ret文字列を逆にします

• ans：=空の文字列、およびi：=0

• i

  • iを1増やします

• fori

  • ans：=ans + ret [i]

• ret：=ans

• retのサイズが0の場合は「0」を返し、それ以外の場合はret

例（C ++）

理解を深めるために、次の実装を見てみましょう-

class Solution {
public:
   string removeKdigits(string num, int k) {
      stack st;
      string ret = "";
      int n = num.size();
      for(int i = 0; i < n; i++){
         while(k && !st.empty() && st.top() > num[i]){
            st.pop();
            k--;
         }
         st.push(num[i]);
      }
      while(k--)st.pop();
      while(!st.empty()){
         ret += st.top();
         st.pop();
      }
      reverse(ret.begin(), ret.end());
      string ans = "";
      int i = 0;
      while(i <ret.size() && ret[i] == '0')i++;
      for(; i < ret.size(); i++)ans += ret[i];
      ret = ans;
      return ret.size() == 0? "0" : ret;
   }
};

入力

"1432219"
3

出力

"1219"