Java solution with a simulated stack in O(N)


  • 0
    X

    The original idea is to simulate a stack in which all characters are kept to return, all others are to be delete.

    The time complexity is O(N), the space complexity is O(1) if we ignore the char array.

    public String removeKdigits(String num, int k) {
            if (num.length() == k) {
                return "0";
            }
            char[] array = num.toCharArray();
            // the point is to delete the first k num[i]
            // that num[i] > num[i + 1]
            // we simulate a stack, end is the top of stack
            // all characters in the stack are what we want to return
            int end = -1;
            int count = 0;
            for (int i = 0; i < array.length; i++) {
                // when do we need to keep array[i] in stack for now
                if (end == -1 || array[i] >= array[end] || count == k) {
                    array[++end] = array[i];
                } else {
                    // when do we need to delete array[end]
                    while (count < k && end >= 0 && array[end] > array[i]) {
                        end--;
                        count++;
                    }
                    array[++end] = array[i];
                }
            }
            // if count < k, all elements in stack is in ascending order
            // we need to pop out the top (k - count) elements
            while (count < k) {
                end--;
                count++;
            }
            // delete all leading zeroes
            int rs = 0;
            for (int i = 0; i <= end; i++) {
                if (array[i] != '0' || rs != 0) {
                    array[rs++] = array[i];
                }
            }
            return rs != 0 ? new String(array, 0, rs) : "0";
        }
    

Log in to reply
 

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