leetcode402. 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 개의 숫자 를 삭제 한 후에 얻 을 수 있 는 최소 결 과 는 얼마 입 니까?
아이디어 와 코드
직관 적 으로 숫자 를 삭제 하고 가장 작은 숫자 를 얻 는 것 은 우리 가 가능 한 한 작은 숫자 를 높 은 위치 에 두 어야 한 다 는 것 을 의미한다. 따라서 우리 가 왼쪽 에서 오른쪽으로 지나 갈 때 이전 숫자 보다 더 작은 숫자 를 만나면 이전 숫자 를 삭제 하고 이 숫자 를 보존 해 야 한다.우리 가 모든 삭 제 를 다 했 을 때, 뒤의 모든 숫자 를 보존 하고, 더 이상 비교 하지 않 는 다.우 리 는 가능 한 한 가장 작은 최고 위 를 얻 었 기 때문에 뒤의 숫자 가 어떻게 값 을 얻 든 지 간 에 가장 높 은 숫자 는 반드시 얻 을 수 있 는 가장 작은 숫자 일 것 이다.예 를 들 어:

10200 k=1
   ： 0 1  ，  0 1 ，          ，    1，  0
   ：          ，          

123450123 k=5
   ：2>1   
   ：3>2   
   : 4>3   
   : 5>4   
   ：0<5   5   0 k=4
   : 0<4   4   0 k=3
   ：0<3   3   0 k=2
   ：0<2   2   0 k=1
   ：0<1   1   0 k=0
   :            ，          

작은 값 을 만 났 을 때 우 리 는 가능 한 한 왼쪽으로 이동 할 것 입 니 다. 왼쪽 값 보다 작고 삭제 횟수 가 남 으 면 왼쪽 값 을 삭제 하면 더 작은 값 을 얻 을 수 있 기 때 문 입 니 다.
코드 는 다음 과 같 습 니 다:

    public String removeKdigits(String num, int k) {
        if(num == null || num.length() == 0 || k==num.length()) return "0";
        Stack stack = new Stack<>();
        for(int i = 0 ; i < num.length() ; i++) {
            char c = num.charAt(i);
            while(k> 0 && !stack.isEmpty() && stack.peek() > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        
        while(k > 0) {
            stack.pop();
            k--;
        }
        
        StringBuilder result = new StringBuilder();
        while(!stack.isEmpty()) {
            result.append(stack.pop());
        }
        while(result.length() > 1 && result.charAt(result.length()-1) == '0') {
            result.deleteCharAt(result.length()-1);
        }
        return result.reverse().toString();
    }