LeetCode 402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:

Input: num = “1432219”, k = 3
Output: “1219”
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:

Input: num = “10200”, k = 1
Output: “200”
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:

Input: num = “10”, k = 2
Output: “0”
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

题目大意:给一个以字符串形式表示的非负整数,从字符串中移除k位,使得剩下的数字尽可能的小~

分析:将字符串中每一个元素放入栈中,如果当前要放入的元素比栈顶元素大,而且k > 0(还需要移除数字),则将栈顶元素弹出后再放入新的元素,因为前面的数字越小越好~等到所有数字都加入栈中后,如果k依旧>0,也就是说还有需要弹栈的数字,那就将最后几位移除,因为前面的数字肯定比后面的数字小~将栈中所有元素放入result字符串中,然后再用index判断第一个不为0的下标为多少,然后截取result为result.substr(index)去除了前导0,如果最后发现result为空则返回”0″,否则返回result~

 

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版