Java贪心算法 删数字问题

问题描述：对给定的n位数字 指定要删除的数字个数 k ，要求删除这k个数之后 ，按照数字原左右顺序 新形成的数字最大

如输入： 5689   1    表示对于5689 删掉一个数字后    得到最大值       

应输出 ： 689

贪心算法核心思想就是 ：总是做出当前最好的选择    

那么要删除每一个数时    都从左侧第一个数（最高位）开始比较每两个数字的大小  如果左侧小于右侧  删除左侧数字    这样就保证了最高位上的数字总是一直在变大的   

比如  21965 这个数  删两位     第一次判断删掉1    第二次判断删除 2    得到结果最优 

贴出代码 ：

public class 删数字问题 {


private static int      k;
private static int[]data;
private static intlength;


public static void test() {
for (int i = 0; i < k; i++) {
boolean isDelete = false; // 判断是否可以覆盖当前数字的标志量
for (int m = 0; m < length - 1; m++) {
if ((data[m] < data[m + 1]) && !isDelete) {
isDelete = true;
}
if (isDelete) {
data[m] = data[m + 1];
}
}
length--; // 不论这个数是不是在遍历的时候是否将isDelete变为true，
      // 循环结束都得将这个长度减1   表示删去了最后的那个数     
}
for (int n = 0; n < length; n++) {
System.out.print("" + data[n]);
}
}


public static void main(String[] args) {
data = new int[50];
Scanner in = new Scanner(System.in);
String data1 = in.nextLine();
length = data1.length();
System.err.println("length = " + length);
k = in.nextInt();
String[] data2 = data1.split("");
for (int j = 0; j < length; j++) {
data[j] = Integer.parseInt(data2[j]);
}
test();
in.close();


}
}

输入的是一个String    然后split  分割成String数组      然后 转为int[] 数组     用全局保存

删除k 个数  就建立一个 for循环，次数为k

内层循环为了遍历这个数    需要注意的是每次循环结束都需要  删去最后的数字   就是length--  ；

length是我设置的全局int  表示当前数组的长度