2022第13届蓝桥杯Java省赛B组 题解 B 山(非暴力!!!)

本解法使用的不是暴力,即使是大题树再大也不怕
1.使用了单调栈判断前一般是单调增字符串
2.使用遍历10-22222中所有满足的情况
3.使用stream流筛选出满足的情况
时间复杂度o(n)

        List ress = new LinkedList<>();
        for (int i = 10; i < 22222; i++) {
            String sb = String.valueOf(i);
            if (!check(sb)) {
                continue;
            }
            int length = sb.length();
            StringBuffer temp = new StringBuffer(sb);
            String reverse = temp.reverse().toString();
            if (length != 5) {
                for (int i1 = 1; i1 < 10; i1++) {
                    String op = sb + i1;
                    if (!check(op)) {
                        continue;
                    }
                    ress.add(op + reverse);
                }
            }
            ress.add(sb + reverse);
        }
        long count = ress.stream().filter(s -> {
            BigDecimal bd = new BigDecimal(s);
            BigDecimal start = new BigDecimal(2022);
            BigDecimal end = new BigDecimal(2022222022);
            return bd.compareTo(start)>=0 && bd.compareTo(end)<=0;
        }).count();
        System.out.println(count);
    }

    //使用栈判断是否为单调
    static boolean check(String s) {
        char[] chars = s.toCharArray();
        Deque stack = new LinkedList<>();
        stack.push(chars[0]);
        for (int i = 1; i < chars.length; i++) {
            if (stack.peek() <= chars[i]) {
                stack.push(chars[i]);
            } else {
                return false;
            }
        }
        return true;
    }