C++でK桁を削除して最小の数値を作るアルゴリズム

負でない整数 num が文字列として与えられているとき、そこから k 桁を取り除き、残った数字で作られる新しい数をできるだけ小さくすることを目指します。例えば、入力が「1432219」で k = 3 の場合、結果は「1219」となります。

この問題は、スタックを活用した貪欲法（グリーディアルゴリズム）によって効率的に解くことができます。

解法のアプローチ

基本となる発想は、「大きい数字がその後ろの小さい数字より先に現れている箇所を優先的に削除する」というものです。文字列を左から右へ走査しながらスタックに数字を積んでいき、スタックの先頭にある数字がこれから読み込む数字より大きい場合は、それをポップ（削除）します。これを繰り返すことで桁の並びが単調増加に近づき、結果として最小の数値が得られます。

アルゴリズムの手順

• スタック st を定義し、空の文字列 ret を用意します。
• n := num のサイズ（文字列の長さ）とします。
• i を 0 から n − 1 までループします。
  • k が 0 でなく、スタックが空でなく、スタックの先頭が num[i] より大きい間、スタックから要素を削除し、k を 1 減らします。
  • num[i] をスタックにプッシュします。
• ループ後も k が 0 でない場合、残りの回数だけスタックから要素を削除します。
• スタックが空になるまで、先頭の要素を ret に追加しながらポップします。
• ret 文字列を反転します（スタックからの取り出し順が逆になるため）。
• ans を空文字列とし、i := 0 とします。
• i が ret のサイズ未満 かつ ret[i] が '0' である間、i を 1 ずつ増やします（先頭の余分な 0 を除去）。
• i 以降の文字をすべて ans に連結し、ret := ans とします。
• ret のサイズが 0 の場合は "0" を返し、それ以外の場合は ret を返します。

C++による実装例

以下の実装例を見ると、動作をより深く理解できます。

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<char> 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;
    }
};

計算量

各桁はスタックに対して高々 1 回のプッシュと 1 回のポップしか行われないため、時間計算量は O(n)、空間計算量も O(n) となります。ここで n は num の桁数です。

入力

"1432219"
3

出力

"1219"