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.
給定一個(gè)用字符串表示的非負(fù)整數(shù)num赦肃，從中移除k位數(shù)字蘸劈，使得剩下的數(shù)字盡可能小党涕。
Notion：
- The length of num is less than 10^5 and will be ≥ k.
- The given num does not contain any leading zero.
Example1:
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.
解題思路：
利用棧（Stack）結(jié)構(gòu)榜配，使得棧中的數(shù)字盡量保持遞增的順序
補(bǔ)充知識(shí)：
str.join()函數(shù)
>>>seq = ['1','2','3','4']
>>>print('.'.join(seq))
1.2.3.4
>>>print(':'.join(seq))
1:2:3:4
print(' '.join(seq))
1 2 3 4
#去掉序列的前綴0
>>>int('001100')
1100
>>>str(int(''001100))
'1100'
代碼：
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
size = len(num)
stack = ['0'] #加上一個(gè)stack['0']是因?yàn)楹竺鎠tack[-1]需要一個(gè)初始值袁梗，'0'是因?yàn)楸容^的對(duì)象為字符型漓帅。
for i in range(size):
while stack[-1] > num[i] and len(stack) > i - k + 1: #不管怎樣num[i]都要進(jìn)棧筹麸，但是在此之前需要判斷上一個(gè)數(shù)字是否需要出棧夭坪。
stack.pop() #如果要進(jìn)棧的數(shù)字小于棧頂元素&&鹦马，棧頂元素出棧胧谈。
stack.append(num[i])
while len(stack) > size - k + 1: #字符串已經(jīng)為遞增型，但是還有沒有刪除夠k個(gè)字符菠红，那就從最后開始刪除大的數(shù)字第岖。
stack.pop()
return str(int(''.join(stack))) #int是去掉序列的前綴0，然后轉(zhuǎn)換成字符型
