Greedy with stack java O(n)


  • 0
    A

    Greedy approach is to remove i-th digits if it is more than the element which is in position i+1. Just implementing this idea will be O(n*k). To optimize the solution till O(n) we can use stack.

    public class Solution {
        public String removeKdigits(String num, int k) {
            Stack<Character> stack = new Stack<>();
            
            for (int i=0; i<num.length(); i++) {
                char c = num.charAt(i);
                while (!stack.isEmpty() && stack.peek()>c && k>0) {
                    stack.pop();
                    k--;
                }
                stack.add(c);
            }
            
            while (k-->0) stack.pop();
            return removeLeadingZeros(stack);
        }
        
        private String removeLeadingZeros(Stack<Character> stack) {
            StringBuilder ret = new StringBuilder();
            boolean isLeadingZero = true;
            for (int i=0; i<stack.size(); i++) {
                if (stack.get(i)=='0' && isLeadingZero) continue;
                isLeadingZero = false;
                ret.append(stack.get(i));
            }
            
            if (ret.toString().isEmpty()) return "0";
            else return ret.toString();
        }
    }
    

Log in to reply
 

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