单调队列

单调队列模板

class MonoticDeque extends ArrayDeque<Integer> {
    BiPredicate<Integer, Integer> isValid;
    Optional<BiConsumer<Integer, Integer>> prev, next;

    public MonoticDeque(BiPredicate<Integer, Integer> isValid) {
        this.isValid = isValid;
    }

    public void push(int n) {
        while (!isEmpty() && !isValid.test(peek(), n)) {
            next.ifPresent(f -> f.accept(pop(), n));
        }
        prev.ifPresent(f -> f.accept(peek(), n));
        super.push(n);
    }
    
    public int max() {
        return peekLast();
    }
    
    public void pollLast(int n) {
        if (n == max()) {
            pollLast();
        }
    }
}

可以用模板，也可以不用，有的时候需要存额外信息，就不用用这个模板

例题四合一

• 316. 去除重复字母（困难）
• 321. 拼接最大数（困难）
• 402. 移掉 K 位数字（中等）
• 1081. 不同字符的最小子序列（中等）

字典序最大的子序列

牛客

给定字符串s，s只包含小写字母，请求出字典序最大的子序列。

请通过代码实现题目，过程中的输入输出处理方式请参考题目输入输出描述或查看语言环境详情。