# 贪心 + 单调栈

若只删除 $1$ 次。

例如： $1432219$ ，那么肯定是删除 $4$

若删除 $4$ 后面的元素 $32219$ 其中一个，那么最后肯定是前缀为 $14\cdots$ 的序列

若删除 $4$ ，那么前缀变成 $13\cdots$ 的序列

二者的长度必然相等，因为都是删除 $1$ 次

贪心地选择删除 $4$

例如： $1452219$ ，那么肯定删除 $5$

对于 $5$ 后面的元素与上述同理

若删除 $5$ 前面的元素 $14$ 其中一个，那么最后 $15\cdots$ 或者 $45\cdots$ 的序列必然大于 $14\cdots$ 的序列

贪心地选择删除 $5$

删除 $5$ 后的序列 $142219$ ，若还可以删除继续删除，那么必然删除 $4$ ，分析同上。

若是连续递增的序列，那么不必删除

若当前元素 $s[i]$ 小于结尾的元素，那么不断地删除结尾的元素直至 $s[i]$ 大于结尾元素，最后将 $s[i]$ 加入结果集的尾部

例如： $145$ ， $s[i] =2$ ，那么需要不断地删除结尾元素 $145\cdots$ 至 $142\cdots$ 至 $12\cdots$

最多只能删除 $k$ 次，若 $k == 0$ 那么可以直接退出循环，将 $s$ 中剩余地元素放入结果集

对于 $1432219$ ， $k = 2$

根据上述步骤删除了 $4,3$ 此时结果集 $12$ ，最后将 $219$ 加入结果集。

为什么不删除 $219$ 其中一个？

上文已经分析了，对于 $3$ ：

若删除 $3$ 以后的元素 $2219$ 其中一个，那么最后肯定是 $143\cdots$ 的序列

若删除 $3$ ，那么最后是 $142\cdots$ 的序列

此时后者必然小于前者，贪心的选择后者，即：删除 $3$

$4$ 也同理

若 $k$ 最后还有剩余，那么可以直接删除尾部的 $k$ 个元素，若结果集不足 $k$ 个，那么直接返回 $0$

我们可以用栈来表示结果集，可以发现这是个单调递增栈。

即：栈顶元素 $peek$ 大于 $s[i]$ ，那么不断地删除栈顶元素并更新 $k=k-1$ 直至栈顶元素 $peek <= s[i]$ 。将 $s[i]$ 压入栈顶。

	class Solution {
	public String removeKdigits(String num, int k) {
	int n = num.length();
	StringBuilder st = new StringBuilder();
	for (int i = 0; i < n; i++) {
	char ch = num.charAt(i);
	while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) >= ch) {
	st.deleteCharAt(st.length() - 1);
	k--;
	}
	// 除去前导零
	if (st.length() > 0 \|\| ch != '0') {
	st.append(ch);
	}
	}
	int len = st.length();
	if (len <= k) {
	return "0";
	}
	return st.substring(0, len - k);
	}
	}

字典序最小

栈单调栈中等贪心字符串

# 贪心 + 单调栈

去除重复字母

拼接最大数