402. Remove K Digits

题目

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个数得出一个最小的数字。
对于一串(n)上升数字来说如果去掉一位数字来得到最小的(n-1)数字去掉最后一位就是他的最小的(n-1)数，

123456789 =>12345678

而 题目输入的 num我们可以看做多个上升序列合成的序列然后我们从i=0开始对i+1判断能否和 i组成上升序列（当num[i]==num[i+1]） 我们也认为能组成上升序列，当遇到i与i+1不能组成上升序列时 remove（i） 并且 i-- 再次判断新的i与i+1能不能组成上升序列 ， 下面数列模拟

1234545678 >123445678 >12344567

代码

fun removeKdigits(num: String, k: Int): String {
    var result = ""
    var nums: ArrayList<Char> = num.toCollection(arrayListOf())
    var index = 0
    var count = 0

    while (count < k && index + 1 < nums.size) {
        if (nums[index] == '0' && index == 0) {
            nums.removeAt(index)
            continue
        }
        if (nums[index + 1] < nums[index]) {
            nums.removeAt(index)
            index--
            if (index < 0)
                index = 0
            count++
        } else {
            index++
        }
    }
    var couut = if (k - count > nums.size) {
        nums.size
    } else {
        k - count
    }
    result = nums.joinToString("").substring(0, nums.size - couut)
    var cout = -1
    for (i in result.indices) {
        if (result[i] != '0') {
            cout = i
            break
        }
    }
    if (cout == -1) {
        cout = result.length
    }
    result = if (cout == result.length)
        ""
    else
        result.substring(cout, result.length)
    if (result == "")
        result = "0"
    println(result)
    return result
}

提交结果

image.png