删除k个数字后，保留最小的数

小编 2026-06-13 阅读:1510 评论:0

介绍如：1593121212去掉3个数，剩下1121212最小。思路如下：删除k个，可以采用贪心算法，每次删除1个那么每次删哪一个呢？若N<2,那就不用纠结了，因为最多只有一个选择若N...

介绍

如：1593121212去掉3个数，剩下1121212最小。
思路如下：
删除k个，可以采用贪心算法，每次删除1个
那么每次删哪一个呢？

若N<2,那就不用纠结了，因为最多只有一个选择
若N>=2,则该整数可以写成XabY，X,Y分别是前缀和后缀，长度可以为0. a，b是相邻的两个数字，且a在b的左边。我们面临的选择就是删除a还是删除b的问题。若删除a，删除后变为XbY; 若删除b，删除后变为XaY.
(1) 若a≠ \\ne
̸

=b，为了让剩下的部分最小，显然我们应该倾向于把a，b中的较大者删掉. 即若a<b, 倾向于删除b; 若a>b,倾向于删除a.
(2) 若a=b, 删除a和删除b是等价的，我们跳过a，比较b和它的后继，又变成问题(1)了。
此时我们已经能看出：
要求剩下的数字最小，从左向右扫描，找出连续的非严格递增串，删除最后一个

要求剩下的数字最大，从左向右扫描，找出连续的非严格递减串，删除最后一个。

实现：

public static String removeKdigits(String num, int k) {
		if(k >= num.length())
			return \"0\";
		
		int newLength = num.length() - k;

		char[] stack = new char[num.length()];

		int top = 0;

		for (int i = 0; i < num.length(); ++i) {
			char c = num.charAt(i);

			while (top > 0 && stack[top - 1] > c && k > 0) {
				top -= 1;
				k -= 1;
			}

			stack[top++] = c;

		}

		int offest = 0;
		while (offest < newLength && stack[offest] == \'0\') {
			offest++;
		}

		return offest == newLength ? \"0\" : new String(stack, offest, newLength - offest);

	}