保留最大的数

import java.util.Scanner;
 /*
   * 123 ,1 升序，就去掉123->23 。
   * 321 ,1 没有升序，从后面去掉321->32.
  */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            StringBuilder sb = new StringBuilder();
            sb.append(sc.next());
            int len = sb.toString().length();
            int cnt = sc.nextInt();
            //异常处理
            if (cnt >= len) {
                System.out.println("0");
            }
            //正常逻辑部分
            int j = 1; //j用来存储之前遍历过的位置
            boolean find = true; //标识这次遍历是否找到过升序的位置
            while (cnt > 0 && find) {
                find = false;
                for (int i = j; i < sb.length(); i++) {
                    int numa = sb.charAt(i - 1) - '0';
                    int numb = sb.charAt(i) - '0';
                    if (numa < numb) {
                        find = true;
                        sb.deleteCharAt(i - 1);
                        cnt--;
                        if (i - 1 > 0) {
                            j = i - 1; //记录上次遍历的位置
                        } else {
                            j = 1;
                        }
                        break;
                    }
                }
            }

            String res = sb.toString();
            if (cnt > 0) {//如果升序对不满足需要，就从后面减去cnt个数
                res = (String) sb.subSequence(0, sb.length() - cnt);
            }
            System.out.println(res);
        }
    }
}

package package1;

import java.util.Scanner;

/**
 * @author jiaqing.xu@hand-china.com
 *         获取最大的保留数
 */
public class Main {

    /**
     * @param originalNumber
     * @param cnt
     * @return int
     */
    public static String getMaxNum(String originalNumber, int cnt) {
        StringBuilder sb = new StringBuilder();
        sb.append(originalNumber);
        //删除几个就循环多少次
        for (int i = 0; i < cnt; i++) {
            int j = 0;
            while (j + 1 < sb.length() && sb.charAt(j) >= sb.charAt(j + 1)) {
                j++;
            }
            //找到该位置小于后一位的数字 则删除之
            sb.deleteCharAt(j);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String originalNumber = scanner.next();
            int cnt = scanner.nextInt();
            System.out.println(getMaxNum(originalNumber, cnt));
        }
    }
}

	

运行时间：133ms
占用内存：11768k

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String a = in.next();
        int b = in.nextInt();
        StringBuilder c = new StringBuilder(a);
        for(int i=0; i<b; i++){
            int flag = 0;
            for(int j=0; j<c.length()-1;j++){
                if(c.charAt(j)<c.charAt(j+1)){
                    flag = 1;
                    c.deleteCharAt(j);
                    break;
                }
            }
            if(flag == 0)
                c.deleteCharAt(c.length()-1);
        }
        System.out.println(c);
    }
}

算法复杂度O(b*n),b是输入的第二个数字，n是第一行字符串a的长度

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String number=sc.next();
int cnt=sc.nextInt();
char[] chss=number.toCharArray();
char[] chs=number.toCharArray();
char[] chs0=new char[chs.length-cnt];;
Arrays.sort(chs);
for(int i=cnt;i<chs.length;i++) { chs0[i-cnt]=chs[i]; } for(int j=0;j<chss.length;j++) { for(int i=chs.length-cnt-1;i>=0;i--) {
if(chss[j]==chs0[i]) {
System.out.print(chs0[i]);
}
}
}
}
测试用例通过20%，之后说运行时间太长，想问问大神们，这个思路是不是正确的呢

通过率只有30%，我的思路是先对那个数进行排序，然后在看需要删除几个元素，就那排序后的数组的前几个元素，查看他们在StringBuffer中对应的角标，然后循环删除。大佬们看看哪有问题

/**     全部通过
保留最大数 ， 位数一定，就让左边的数尽可能的大 
用i循环 ，保证i前边没有比i大的数，i后移， 
i = 1~length length 是一个变值 这里只是保证 从大到小排序后，又循环到队尾可以退出
 */
public class Main {
    public static void main(String[] args) {
        // 输入
        Scanner sc = new Scanner(System.in);
        String num = sc.nextLine();
        int n = sc.nextInt();
        // 处理
        String[] ss = num.split("");
        List list = new ArrayList();
        list.addAll(Arrays.asList(ss));
        // 1、保证 从大到小序列
        for (int i = 1; i < ss.length; i++) {// length 是变值这里只是保证从大到小排序后又循环到队尾可以退出
            if (n == 0) {
                break; // 去除 n 位后退出
            }
            while (i > 0 && i < list.size()// 保证不越界
                    && list.get(i).compareTo(list.get(i - 1)) > 0) { // 循环保证 i前边没有比他大的数
                if (n == 0) {
                    break; // 去除 n位后退出
                }
                list.remove(i - 1);
                i--; // 去除前边的 i指向的下标要 减一
                n--;
            }
        }
        // 2、 位数不够接着从尾部取
        while (n > 0) {// 如果去到 list已经从大到小排序，位数还不够n 就接着 从尾部取
            list.remove(list.size() - 1);
            n--;
        }
        String res = "";
        for (String s : list) {
            res += s;
        }
        System.out.println(res);
    }
}

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[] str = scanner.next().toCharArray();
        int n = scanner.nextInt();
        
        System.out.println(getResult(str, n));
    }
    
    public static char[] getResult(char[] str, int n) {
        if (str.length == n) {
            return null;
        }
        if (n == 0) {
            return str;
        }
        //System.out.println(str);
        //System.out.println(n);
        
        int index = -1;
        int max = -1;
        for (int i = 0; i < n + 1; i++) {
            if ((str[i] - '0') > max) {
                max = str[i] - '0';
                index = i;
                //System.out.println(max + " " + i);
            }
        }
        
        char[] result;
        if (index == 0) {
            char[] temp = new char[str.length - 1];
            for (int i = 1; i < str.length; i++) {
                temp[i - 1] = str[i];
            }
            char[] t = getResult(temp, n);
            int length;
            if (t == null) {
                length = 0;
            } else {
                length = t.length;
            }
            result = new char[length + 1];
            result[0] = str[0];
            for (int i = 1; i < result.length; i++) {
                result[i] = t[i - 1];
            }
            n = n - str.length + result.length;
        } else {
            result = new char[str.length - index];
            for (int i = 0; i < result.length; i++) {
                result[i] = str[i + index];
            }
            n = n - index;
        }
        
        
        return (getResult(result, n));
    }
}

/** JAVA 100%CASE通过 代码
 * 思路如下:
 *      从高位开始，每一位的数肯定最大最好。
 *  所以从头查找最大的数。把这个数作为高位，那么这个数就是最大的。
 *  比如：
 *    32918654321 去掉4个数
 *    step1:
 *            从9开始递减，查看第一位最大的数可能是多少
 *            我们查询到第一次出现9的位子下标为2.
 *            这个9前面有2个数比9小，那么如果把9作为第一位的话，那么结果肯定是最大的。
 *          (exception:如果没找到9，则找8,依次递减)
 *    step2:
 *            所以，继续判断，如果9前面的个数是否小于等于要删除的个数。
 *            2<4，说明我们有这么多个数可以删除。
 *          (exception:如果前面的个数大于要去掉的个数，那么这个数就不能作为高位了，就只能退而求其次选择比这个数小的作为高位)
 *    step3:
 *            删除9前面的数 得到数 918654321 由于第一位9已经确定了。
 *            那么我们的需求就变成： 
 *            18654321 去掉2个数
 *    step4:
 *            如果剩下的数的个数正好等于要去掉的个数，那么前面的高位组合就是答案了。
 *            如果剩下的数的个数大于要去掉的个数
 *                且  如果  要去掉的个数为0,那么结束循环，把前面的所有高位和剩下的数组合就是答案了。
 *                    反之，要去掉的个数大于0,则把这个再次带入step1进行循环，
 */
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String num = in.nextLine();
    int n = Integer.parseInt(in.nextLine());
    int count = 0;
    while(count<n){
        for(int i=9;i>=0;i--){
            int p = num.indexOf(i+"");
            if(p!=-1&&p<=n-count){
                System.out.print(i);
                count+=p;
                num = num.substring(p+1);
                if(num.length()==n-count){
                    return;
                }
                break;
            }
        }
    }
    System.out.println(num);
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            StringBuilder sb = new StringBuilder();
            sb.append(scanner.next());
            int cnt = scanner.nextInt();
            int count = 0;
            while (count < cnt) {
                int len = sb.length() - 1;
                int s = 0;
                while (s < len && sb.codePointAt(s) >= sb.codePointAt(s+1))
                    s++;
                sb.deleteCharAt(s);
                count++;
            }
            System.out.println(sb.toString());
        }
    }
}

有个测试用例就一个参数？怎么破？

import java.util.*;

public class Main {
    String maxNumberLeft(String num,int cnt){
        StringBuffer sb = new StringBuffer(num);
        for(int i = 0; i < cnt; i++){
            for (int j = 0; j < sb.length(); j++){
                if (j == sb.length() - 1) {
                    sb.deleteCharAt(j);
                }else if (sb.charAt(j) < sb.charAt(j+1)){
                    sb.deleteCharAt(j);
                    break;
                }
            }
        }
        return sb.toString();
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String number = sc.next();
            int cnt = sc.nextInt();
            System.out.println(new Main().maxNumberLeft(number,cnt));
        }
        sc.close();
    }
}

从左到有遍历一遍，找到比下一个小的移除同时count--，(下一次比较的应该是被移除的数前后这两个数)然后遍历的i=i-2（如果被移除的是第一位则i--）。这样循环一次完成，number肯定是处理成递减排列的，如果count还有富余，则在number的末尾砍掉count位

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        List list = new ArrayList();
        for (int i = 0; i < str.length(); i++) {
            list.add(Integer.valueOf(str.charAt(i)+""));
        }
        int count = scan.nextInt();
        for (int i = 0; i 0; i++) {
            if(list.get(i)<list.get(i+1)){
                list.remove(i);
                count--;
                i--;
                if(i>=0) i--;    //除了被移除的是首位，继续减1
            }
        }
        for (int i = 0; i < list.size()-count; i++) {
            System.out.print(list.get(i));
        }
    }

import java.util.Scanner;

/**
 * *首先吐槽case 测试用例:
 * 3976586154020523962300880671964737778724593606571242584991494668986229285835291323002908476867960200646623388326122235670893738530103282358714444924437904136100327756180675360227395260460902778910380553989589407298751034527862336552985549014484926749942542931303831688603585104852008564203001516929722841936724919564733343000912953826068636786812551774440587188100767280174282302956457303029335254090938764250923672658479458507598811673816450969288929290113827748307621358877175736571006952739887939779548366860431383332468412878953844996902652841019937061686417655296026967227612000982875584291377048376306999211221228707788460070158713409718659728103431119166434817373338512809761785488301165503395293541807035591162020062423434932626586243185307679015262113777220009903281336403825118583385492139204588138428488471867382445787993410086452111592394238701919275231300991366935422555313522331690511292885698171474094128521344957015676199943569717927580485837043452276380024935291558140228836214243228630830642
 * 我做了处理 还是不给过 这就让我很郁闷了
 * 
 * 思路：转换成StringBuffer 从左到右寻找左边比右边小的数，
 * 找到后用replace方法去掉 退出当前循环，当循环到最后的时候还没找到
  * 那么就去掉最后一个数。
 *  下一次循环从上一次结束的位置开始，因为前面的在之前的循环里面已经判断
 * 
 *
 */

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String innum = in.nextLine();
        if (innum.length() < 1000) {
            int num = 1;
            StringBuffer a = new StringBuffer();
            a.append(innum);
            int time = in.nextInt();
            if (time >= 1 || time < a.length()) {
                num = 1;
                for (int i = 0; i < time; i++) {
                    for (; num < a.length(); num++) {
                        if (a.charAt(num) > a.charAt(num - 1)) {
                            a.replace(num - 1, num, "");
                            break;
                        }
                        if (num == (a.length() - 1)) {
                            a.replace(num, num + 1, "");
                            num--;
                            break;
                        }
                    }
                }
                System.out.println(a);
            }
        }else {
            System.out.println("no");
        }
    }
}

public class KeepMaxNumber {

    //思路：从头开始删
    //如果number[i]>=number[i+1] i向后移一位
    //如果number[i]<number[i+1] 删除number[i]，且此时要把i向前移一位

    public static  String getMaxResult( StringBuilder number, int cnt){

        int len = number.length();
        if (cnt >= len) return String.valueOf(0);

        int i = 0 ;
        while (cnt !=0 && i < number.length()-1){
            if ( cnt > 0 && number.charAt(i) < number.charAt(i+1) ){
                number.deleteCharAt(i);
                cnt--;
                i--  ;
                if (i <0){
                    i = 0;
                }
            }else {
                i++;
            }
        }
        return number.toString().substring(0,number.length()-cnt);
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String number = in.next();
            int cnt = in.nextInt();
            StringBuilder sb = new StringBuilder(number);          
            String res = getMaxResult(sb,cnt);
            System.out.println(res);
        }

    }
}