Straightforward Java Solution Using Stack


  • 46
    Z
    public class Solution {
        public String removeKdigits(String num, int k) {
            int len = num.length();
            //corner case
            if(k==len)        
                return "0";
                
            Stack<Character> stack = new Stack<>();
            int i =0;
            while(i<num.length()){
                //whenever meet a digit which is less than the previous digit, discard the previous one
                while(k>0 && !stack.isEmpty() && stack.peek()>num.charAt(i)){
                    stack.pop();
                    k--;
                }
                stack.push(num.charAt(i));
                i++;
            }
            
            // corner case like "1111"
            while(k>0){
                stack.pop();
                k--;            
            }
            
            //construct the number from the stack
            StringBuilder sb = new StringBuilder();
            while(!stack.isEmpty())
                sb.append(stack.pop());
            sb.reverse();
            
            //remove all the 0 at the head
            while(sb.length()>1 && sb.charAt(0)=='0')
                sb.deleteCharAt(0);
            return sb.toString();
        }
    }
    

  • 0
    C

    nice solution and easy to follow!


  • 3
    M

    while(k>0){ stack.pop(); k--; }
    The function of this part of code is :
    1. in case of 11111 (duplicate)
    2. in case of 12345 (ascending order number)


  • 1
    F

    @macctown Agreed. The loop only removes digits in stack that are ascending and larger than current digit. It won't remove anything if the digits are non-descending.


  • 0
    L

    Good solution and easy to understand! Thanks for sharing.


  • 5
    S

    Great solution! Pretty easy to understand. Just one suggestion though.

    Instead of performing a reverse first and then removing the characters at head, you could remove the characters at the tail and then reverse the string.

    deleteCharAt is a linear time operation. If you remove a character at the head, the characters will have to be moved forward by one position each time. On the other hand, removing the tail character can be achieved in constant time as there would be no shifting involved! :)

    The change can be incorporated as follows:

    while(sb.length() > 1 && sb.charAt(sb.length()-1) == '0')
                sb.deleteCharAt(sb.length()-1);
    
    return sb.reverse().toString();
    

  • 0
    C

    really a good and self-explain solution, thx


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.