Java O(n), variant of monotonic increasing queue


  • 0
    D
    public class Solution {
        public String removeKdigits(String num, int k) {
            if (num == null || num.length() == 0) {
                return num;
            }
            int n = num.length();
            assert n >= k;
            if (n == k) {
                return "0";
            }
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < n; i++) {
                char ch = num.charAt(i);
                while (stack.size() > 0 && stack.size() + n - i - 1 >= n - k && stack.peek() > ch) {
                    stack.pop();
                }
                if (stack.size() < n - k) {
                    stack.push(ch);
                }
            }
            int index = 0;
            while (stack.get(index) == '0' && index < stack.size() - 1) {
                index++;
            }
            StringBuffer sb = new StringBuffer();
            for (; index < stack.size(); index++) {
                sb.append(stack.get(index));
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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