# encoding=utf-8

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """

        # 特殊情况
        if k == 0:
            return num
        if k == len(num):
            return "0"

        # 将num转换为list好处理，结果：123  --> ["1","2","3"]
        num = list(num)

        # 循环k趟，每趟去掉一位数，所以一共去除k位数
        while k > 0:
            flag = 1

            # 如果num[idx] > num[idx + 1]，那么应该去掉 num[idx]
            for idx in range(len(num) - 1):
                if num[idx] > num[idx + 1]:
                    num.pop(idx)

                    k -= 1
                    flag = 0
                    break

            # 如果这一趟没有找到，那么意思就是对每一个位置，都有num[idx] <= num[idx + 1]，那么此时，去掉最后一位上的数，剩下的数组成的当前趟的新数就是最小的，因为当前趟最后一个数是最大的。
            if flag == 1:
                k -= 1
                num.pop(-1)

        # 去除结果中的前导0。
        while len(num) > 0:
            if num[0] == "0":
                num.pop(0)
            else:
                break

        # 有可能走完k趟，并且去掉前导0后，num就为空了，此时需要返回0. 例如：num=1000   k=1
        if len(num) == 0:
            return "0"
        else:
            return "".join(num)

# print Solution().removeKdigits(num="112", k=1)

2.同理也可以寻找最大数：即n位数去除m位数，使得剩下的数组成的新数最大，原理同上，只改一个条件即可。

即将  if num[idx] > num[idx + 1]  改为：  if num[idx] < num[idx + 1]   即可。

# encoding=utf-8
'''
leetcode402 是n位数去除m位数剩下的数最小，那么同理也可以做n位数去除m位数剩下的数最大

'''


class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """

        # 特殊情况
        if k == 0:
            return num
        if k == len(num):
            return "0"

        # 将num转换为list好处理，结果：123  --> ["1","2","3"]
        num = list(num)

        # 循环k趟，每趟去掉一位数，所以一共去除k位数
        while k > 0:
            flag = 1

            # 如果num[idx] < num[idx + 1]，那么应该去掉 num[idx]
            for idx in range(len(num) - 1):
                if num[idx] < num[idx + 1]:
                    num.pop(idx)

                    k -= 1
                    flag = 0
                    break

            # 如果这一趟没有找到，那么意思就是对每一个位置，都有num[idx] >= num[idx + 1]，那么此时，去掉最后一位上的数，剩下的数组成的当前趟的新数就是最大的，因为当前趟最后一个数是最小的。
            if flag == 1:
                k -= 1
                num.pop(-1)

        # 去除结果中的前导0。
        while len(num) > 0:
            if num[0] == "0":
                num.pop(0)
            else:
                break

        # 有可能走完k趟，并且去掉前导0后，num就为空了，此时需要返回0. 例如：num=1000   k=1
        if len(num) == 0:
            return "0"
        else:
            return "".join(num)

print Solution().removeKdigits(num="1008908",k=5)