O(n) solution with monotonic queue


  • 0
    L

    Each digit in num is inserted into queue once and removed from queue at most once, so the total time complexity is O(n)

    public class Solution {
        public String removeKdigits(String num, int k) {
            int queueLen = num.length() - k;
            List<Integer> monotonic = new ArrayList<Integer>(queueLen);
            for (int i = 0; i < num.length(); i++) {
                int cur = num.charAt(i) - '0';
                int left = num.length() - i;
                while (!monotonic.isEmpty() && monotonic.get(monotonic.size() - 1) > cur && monotonic.size() + left > queueLen) {
                    monotonic.remove(monotonic.size() - 1);
                }
                if (monotonic.size() < queueLen) {
                    monotonic.add(cur);
                }
            }
            StringBuilder sb = new StringBuilder();
            boolean leadingZero = true;
            for (int i = 0; i < monotonic.size(); i++) {
                if (monotonic.get(i) != 0) {
                    leadingZero = false;
                }
                if (!leadingZero) {
                    sb.append(monotonic.get(i));
                }
            }
            if (sb.length() == 0) {
                return "0";
            } else {
                return sb.toString();
            }
        }
    }
    

Log in to reply
 

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