402. Remove K Digits

leetcode medium

#array#csharp#leetcode#medium#stack#string#tree

Task

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: num = "1432219", k = 3

Output: "1219"

C# solution

matched/original

public class Solution {
    public string RemoveKdigits(string num, int k) {
        Stack<char> stack = new Stack<char>();
        foreach (char digit in num) {
            while (k > 0 && stack.Count > 0 && stack.Peek() > digit) {
                stack.Pop();
                k--;
            }
            stack.Push(digit);
        }
        char[] resultArray = stack.ToArray();
        Array.Reverse(resultArray);
        string result = new string(resultArray).Substring(0, resultArray.Length - k).TrimStart('0');
        return result == "" ? "0" : result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string RemoveKdigits(string num, int k) {
        stack<char> stack = new stack<char>();
        foreach (char digit in num) {
            while (k > 0 && stack.size() > 0 && stack.Peek() > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }
        char[] resultArray = stack.ToArray();
        Array.Reverse(resultArray);
        string result = new string(resultArray).Substring(0, resultArray.size() - k).TrimStart('0');
        return result == "" ? "0" : result;
    }
}

Java solution

matched/original

public class Solution {
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();
        for (char digit : num.toCharArray()) {
            while (k > 0 && !stack.isEmpty() && stack.peek() > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }
        while (k > 0) {
            stack.pop();
            k--;
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        result.reverse();
        while (result.length() > 1 && result.charAt(0) == '0') {
            result.deleteCharAt(0);
        }
        return result.length() == 0 ? "0" : result.toString();
    }
}

JavaScript solution

matched/original

class Solution {
    removeKdigits(num, k) {
        const stack = [];
        for (const digit of num) {
            while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
                stack.pop();
                k--;
            }
            stack.push(digit);
        }
        stack.splice(stack.length - k, k);
        let result = stack.join('');
        while (result.length > 1 && result[0] === '0') {
            result = result.slice(1);
        }
        return result === '' ? '0' : result;
    }
}

Python solution

matched/original

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        final_stack = stack[:-k] if k else stack
        return ''.join(final_stack).lstrip('0') or '0'

Go solution

matched/original

func removeKdigits(num string, k int) string {
    stack := []byte{}
    for i := 0; i < len(num); i++ {
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, num[i])
    }
    stack = stack[:len(stack)-k]
    result := string(stack)
    for len(result) > 1 && result[0] == '0' {
        result = result[1:]
    }
    if result == "" {
        return "0"
    }
    return result
}

Explanation

Algorithm

Инициализация:

Создайте стек для хранения цифр, которые будут образовывать минимальное число.

Обработка каждой цифры:

Перебирайте каждую цифру в строке num.

Если текущая цифра меньше верхней цифры в стеке и у вас есть еще возможность удалить цифры (k > 0), удалите верхнюю цифру из стека.

Добавьте текущую цифру в стек.

Удаление оставшихся цифр:

Если после прохождения всей строки k еще больше нуля, удалите оставшиеся цифры из конца стека

Формирование результата:

Постройте итоговое число из цифр в стеке и удалите ведущие нули.

😎