411. Remove K Digits to Get Smallest Number (LL + Stack)

Given a non-negative number represented as a linked list of digits (most significant first) and an integer k, remove exactly k digits so that the resulting number is the smallest possible. Return the result as a string with no leading zeros (return "0" if the result is empty). Input: '[digits], k'.

Input: '[digits], k'.

Output: Quoted string — the smallest resulting number.

Examples

Input: [1,4,3,2,2,1,9], 3
Output: "1219"
Explanation: Remove 4,3,2 to get 1219.

Input: [1,0,2,0,0], 1
Output: "200"
Explanation: Remove 1, strip leading zero.

Input: [1,0], 2
Output: "0"
Explanation: Everything removed.

Constraints

• 1<=n<=10^5
• 0<=k<=n
• digits 0-9

Asked by