[問題]n位整數拿掉m數字得到最大數值

[PATRICKSTARS (PatrickStar)]

Given an integer (not necessary a decimal number) with n digits, we want to
remove m (<=n) digits from this number such that the resulting number is as
large as possible. Design an O(n) time algorithm to solve it.

可以提示如何下手嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.251.105.172
推 guest2:找出第m大的數字，拿掉比他小的
推 guest2:錯了remove m digits應該是保留比第m個大的
→ PATRICKSTARS:這樣有辦法O(n)嗎? 是否可有詳細的解釋QQ
→ scwg:一樓的作法對 231, 拿掉一個位數會錯: 23 < 31
推 CaptainH:RMQ
推 CaptainH:預處理O(n)+m次O(1)查詢=O(n)
推 guest2:謝謝S大提醒。C大可以說的清楚點嗎?
推 pigalan:C大的做法應該是每次找從前數m'個第一次出現的最大digit吧
→ pigalan:這樣的話可以不用RMQ 畢竟O(n)預處理RMQ太刺激了www
推 pigalan:有個想法~可以從左到右用非嚴格遞減stack,直到pop m個為止
推 suhorng://tioj.redirectme.net:8080/JudgeOnline/showproblem?
→ suhorng:problem_id=1397      據說是...
推 pigalan:慘了原來出過這題=口= 感謝樓上QQ
推 atoi:UVa的11491-Erasing and Winning 也是這題喔