题解 | #移掉 K 位数字# [P0]

单调递增栈

import java.util.*;

public class Solution {
    // 找左边最小: 从左往右 单调递增栈
    public String removeKnums (String num, int k) {
      if (num.length() <= k) return "0";
      
      StringBuilder sb = new StringBuilder();
      // stack grows to the right
      Deque<Character> dq = new ArrayDeque<>();
      for (int i = 0; i < num.length(); i++) {
        char cur = num.charAt(i);
        // 保证单调递增
        while (!dq.isEmpty() && dq.peekLast() > cur)
          dq.removeLast(); 

        dq.offerLast(cur);
        
        if (i >= k) {
          char first = dq.pollFirst();
          // 不要前缀的0
          if (!(sb.length() == 0 && first == '0')) {
            sb.append(first);
          }
        } 
      }
      return sb.length() == 0 ? "0" : sb.toString();
    }
}