題目連結:
題目大意:
給定一串數字(長度不超過 36, 000, 000 ),並給定一正整數N。
求在不更動員有數字串之給定順序之下,挑選 N 個數所組成的可能最大的數之值。
範例輸入:
987645821 6
123456789 8
95655645 1
範例輸出:
987821
23456789
9
解題思維:
以範例輸入的第一筆之 987645821 6 為例,藍色代表目前存取的數字,紫色代表目前已經選的數字:
987645821
首先,第一個數字為 9 ,先挑就對了。
987645821
再來是 8 ,沒有大於 9 ,所以也挑。
987645821
再來是 7 ,沒有大於 8 ,所以也挑。
987645821
再來是 6 ,沒有大於 7 ,所以也挑。
987645821
再來是 4 ,沒有大於 6 ,所以也挑。
987645821
再來是 5 ,大於 4 ,所以把已挑選的 4 替換成 5 。
987645821
再來是 8 ,大於 5 ,也大於 6 。雖然也大於 7 ,但是剩下的數字剛好可以填成長度為 6 的數字,所以剩下全挑。因此最終結果為:
987645821
以上,我們可以觀察出:
當目前的數字,大於目前挑的數字的尾端時,就刪掉最後面的數,重複此步驟直到不大於尾端數字。然後就接在後面。但是要注意剩下的數字之數量,倘若剩下的數字剛好可以填補剩下的空隙,就全部都挑。
然後判斷一下特殊狀況(要挑的數字長度大於給定的數字串之長度之類……)即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。