Java solution using stack


  • 0
    S
    /**
     *Basic idea:
     * The idea is borrowed from [239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/).
     * Scan the array of digits from left to right. We sill push some of them into a stack.
     * During the scan, pop elements until the current digit is not less than the top of stack. The poped digits are those removed digits.
     * Then push the current digit to the stack.
     * The essence is that when you find a digit greater than already scanned digit(s), and if you can still remove some digit(s),
     * you know you can remove those greater digits in order to make the final number smaller. After all, the length of
     * the final number is deterministic.
     * Note that:
     * - The digits in the stack are always in (non-strictly) increasing order.
     * - Do not remove more than k digits. Stop the scan when necessary.
     * - In my code, I push the index of digits rather than the digits themselves into the stack.
     *Result:
     * 30 / 30 test cases passed.
     * Status: Accepted
     * Runtime: 13 ms
     * Your runtime beats 75.54% of java submissions.
     *Date:
     * 10/4/2016
     */
    public class Solution {
        public String removeKdigits(String num, int k){
            if(num==null || num.length()<=k){
                return "0";
            }
            int toBeRm = k;
            Stack<Integer> stack = new Stack<>();
            for(int i=0;i<num.length() && toBeRm>0;i++){
                while(toBeRm>0 && !stack.isEmpty() && num.charAt(i)<num.charAt(stack.peek())){
                        int r = stack.pop();
                        toBeRm--;
                }
                stack.push(i);
            }
            StringBuilder sb = new StringBuilder();
            int i=0;
            for(int index : stack){
                if(i>=num.length()-k)
                    break;
                sb.append(num.charAt(index));
                i++;
            }
            if(stack.size()<num.length()-k){
                sb.append(num.substring(k+stack.size()));
            }
            String res = sb.toString();
            return trimLeadingZero(res);
        }
        private String trimLeadingZero(String num){
            for(int i=0;i<num.length();i++){
                if(num.charAt(i)!='0'){
                    return num.substring(i);
                }
            }
            return "0";
        }
    }
    

Log in to reply
 

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