Remove K Digits
数字の文字列として表された非負の数 num と、整数 k が与えられます。ちょうど k 桁を削除し、残りの桁の順序を保ったまま、残った数ができるだけ小さくなるようにします。
先頭のゼロを除いた文字列として返してください。何も残らない場合、またはゼロだけが残る場合は、"0" を返してください。
関数
- numstring
- 数字で表記された数値
- kinteger
- 削除する桁数
- 戻り値string
- 先頭にゼロを付けず、文字列として表した、使用できる最小の数
制約
1 ≤ num.length ≤ 4 × 1040 ≤ k ≤ num.lengthnumには0から9までの数字だけが格納されます。numには、数値そのものがゼロである"0"の場合を除き、先頭にゼロはありません。
例
- 入力
- num = "4325043"k = 3
- 出力
- "2043"
- 説明
- 4と最初の3を取り除くと、2が先頭になります。0を先頭にすることはできません。0の前には4桁あり、取り除けるのは3桁だからです。最後に取り除くのは5です。5は、それより小さい0の前にあります。
- 入力
- num = "30200"k = 1
- 出力
- "200"
- 説明
- 3を削除すると
0200となり、先頭のゼロを取り除くと200になります。それ以外の削除では3が先頭に残り、3000のような4桁の数になります。
- 入力
- num = "52"k = 2
- 出力
- "0"
- 説明
- 2つの数字はどちらも取り除かれるため、何も残らず、答えは
"0"です。
発展問題
解をどのように変更すれば、k 桁を削除して、代わりに最大の数を残せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
k桁を取り除く方法がどれであっても、残る桁数は同じです。同じ桁数の2つの数では、異なる最初の桁によって、どちらが小さいかが決まります。どの桁をできるだけ小さくすることに最も力を入れるべきでしょうか？数字を左から読みます。ある桁がその直後の桁より大きい箇所が初めて見つかったとき、その桁を削除すると、最も左側の可能な位置で数値を小さくできます。桁が一度も小さくならない場合は、最後の桁を削除します。
残すことにした数字はスタックに保持します。新しい数字をプッシュする前に、削除回数が残っている間、スタックの先頭からより大きな数字をすべてポップします。最後に、残っている削除回数分だけスタックの先頭から取り除き、その後、先頭のゼロを削除します。
解説
最も左の桁が最も大きな重みを持つため、右隣の桁より大きい最初の桁を取り除きます。残す桁をスタックに積めば、このルールを文字列全体に1回の走査で適用できます。最後に残った削除回数分は末尾から取り除き、最後に先頭のゼロを取り除きます。
一度に1桁ずつ削除する
正しいが、最大のテストでは終わらない
考え方
1 桁ずつ削除します。num[i] > num[i+1]となる最初の位置iを見つけてnum[i]を削除します。桁が一度も小さくならない場合は、最後の桁を削除します。これをk回繰り返します。
どの答えもn-k桁なので、2つの答えが異なる最初の位置によって、どちらが小さいかが決まります。iまでの桁は小さくならないため、それより前の桁を削除すると、少なくとも同じ大きさの桁が繰り上がってきます。後ろの桁を削除すると、大きいnum[i]がそのまま残ります。num[i]を削除すれば、小さくできる最初の位置を小さくできます。
削除のたびに左から再走査し、その後ろの桁をずらすため、処理量はO(n·k)です。k = 25,000のとき、40,000個の1に対する走査では約6.9 × 10^8桁を読み取ります。
アルゴリズム
- 数字を、削除できるリストにコピーします。
k回繰り返します。左から進み、次の桁より大きい最初の桁、または最後の桁まで進んで、その桁を削除します。- 先頭のゼロを取り除き、何も残らなければ
"0"を返します。
def removeKdigits(num, k):
digits = list(num)
for _ in range(k):
# Find the first digit that is bigger than the digit after it.
# If the digits never go down, i stops on the last digit.
i = 0
while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
i += 1
del digits[i]
result = "".join(digits).lstrip("0")
return result if result else "0"保持される数字の単調スタック
考え方
遅いバージョンで num[i] を削除した後も、i より前の桁は決して減少しないため、次に削除できるのは隙間の直前の桁からです。スタックにはその接頭部分、つまり残した桁を格納します。スタックの下から上に向かって、桁は減少しません。新しい桁がスタックの先頭より小さい場合、その先頭の桁は右隣の桁、つまり遅いバージョンで削除される桁より大きくなっています。その桁を取り出して削除回数を1つ使い、新しい先頭がまだ大きければ、取り出し続けます。
4325043 に対して k = 3 の場合、3で4を取り出し、2で3を取り出し、0で5を取り出します。4と3は順に到着したときにスタックに追加されるので、結果は 2043 です。
各桁は1回ずつ追加され、取り出しのたびに k 回の削除のうち1回を使うため、この処理は O(n) です。
アルゴリズム
- 空の数字スタックを作成します。
numの各桁について、削除回数が残っていて、スタックの一番上の値がその桁より大きい間、一番上の値を取り出して削除回数を1回消費します。その後、その桁をプッシュします。- ループ後も削除回数が残っている場合は、その回数分だけスタックの一番上から数字を削除します。
- スタックを下から上へ読み取り、先頭のゼロをスキップして、残りを返します。何も残っていない場合は
"0"を返します。
def removeKdigits(num, k):
stack = [] # kept digits, never decreasing from bottom to top
for digit in num:
# A bigger digit right before a smaller one: dropping it makes the number smaller.
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# The kept digits never decrease, so any removals left come off the end.
stack = stack[:len(stack) - k]
result = "".join(stack).lstrip("0")
return result if result else "0"
落とし穴と境界ケース
- 先頭の数字が新しい数字と等しいときに取り除くこと。
k = 1の112では12が残りますが、正解は11です。 - ループの後に残った削除回数を使い切るのを忘れること、または先頭から削除すること。スタックが減らないため、最後の数字は次のようになります。
k = 3の123456789では123456になります。 - 取り除かれた先頭のゼロを削除回数に数えること。
k = 1の100200では、削除するのは1だけです。先頭のゼロは削除回数を消費せず、答えは200です。 - 空文字列を返すこと。
k = 1の10ではゼロだけが残るので、答えは"0"です。 numを整数に変換すること。桁数は4 × 10^4にもなり、どの整数型の範囲もはるかに超えるため、数字を文字として比較してください。
よくある質問3
Remove K Digits の時間計算量はどれくらいですか？
単調スタックを使うと、n 桁に対して実行時間は O(n) です。各桁は一度だけプッシュされ、各ポップ操作で k 回の削除のうち1回を行います。スタックには最大 n 桁が保持されるため、追加の領域は O(n) です。削除のたびに左から再走査すると、O(n·k) のコストがかかります。
Remove K Digits では先頭のゼロをどのように処理しますか？
まず数字を削除し、ゼロを取り除くのは最後だけにします。先頭のゼロは値を変えないため、削除回数には数えません。k = 1 のとき、10200 は 0200 になり、その後 200 になります。ゼロを取り除いた結果、何も残らなければ "0" を返します。
K 個の桁を削除する問題は、追加の O(1) 空間で解けますか？
はい、入力を変更してもよい場合です。スタックに格納される桁数は、読み取った桁数を超えることがないため、スタック自体を数字配列の先頭部分に置き、1つのインデックスでそのトップを管理できます。不変文字列を使う言語でも、数字を1回コピーする必要があり、その計算量は O(n) です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def removeKdigits(num, k):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
num = "4325043" k = 3
期待される出力
"2043"