小美的代金券要过期啦

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        int n =scanner.nextInt();
        int[] nums =new  int[n];
        for (int i = 0; i < n; i++) {
            nums[i] =scanner.nextInt();
        }
        int res=0;


        for (int j = 1; j < n; j++) {
            if(nums[j-1]==nums[j]){
                res++;
                nums[j]=nums[j-1]+1;
                nums[j-1]=-1;
                for (int k = j-1; k >=0 ; k--) {
                    if(nums[k]!=-1){
                        if(nums[j]==nums[k]){
                            res++;
                            nums[j]=nums[j]+1;
                            nums[k]=-1;
                        }else {
                            break;
                        }
                    }
                }


            }


        }
        System.out.println(res);
    }
}

双指针+数组(System.arraycopy)

直接判断nums[index] he nums[index+1]相不相等，不相等index++，相等将nums[index]++, 并将数组的右边的所有值左移（arraycopy不会太慢）然后将index回溯一个(不为0的时候)，再继续匹配。

实际上本来应该用双向链表做的，这里是用数组模拟。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i=0; i<n; i++) {
            nums[i] = in.nextInt();
        }
        int index = 0;
        int end = n-1;
        int mergeTimes = 0;
        while(index < end) {
            if (nums[index] != nums[index+1]) {
                index++;
                continue;
            }
            nums[index] = nums[index] + 1;
            if (index < end -1) {
                System.arraycopy(nums, index+2, nums, index+1, end-(index+1));
                // end--;就可以了，将nums[end]设为零主要是调试好看
                nums[end--] = 0;
            }
            if (index > 0) {
                index--;
            }
            mergeTimes++;
        }
        System.out.println(mergeTimes);
    }
}

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.valueOf(br.readLine());
        String[] s=br.readLine().split(" ");
        Stack<Integer> stack=new Stack<>();
        stack.push(Integer.valueOf(s[0]));
        int res=0;
        for(int i=1;i<n;i++){
           int tmp=Integer.valueOf(s[i]);
           while(stack.size()!=0 && tmp==stack.peek()){
               res++;
               stack.pop();
               tmp++;
           }
           stack.push(tmp); 
        }
        System.out.println(res);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[]a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        System.out.println(n-helper(a));
    }
    public static int helper(int[]a){
        if(a.length<=1)
            return a.length;
        int p = Integer.MAX_VALUE;
        int m =Integer.MAX_VALUE;
        int n = a.length;
        for(int i=0;i<n;i++){
            m = Math.min(m,a[i]);
        }
        int j = -1;
        int k = 0;
        for(int i=0;i<n;i++){
            if(a[i]==m&&j==-1){
                j = i;
                k = j;
                while(k+1<n&&a[k+1]==m){
                    k++;
                }
                break;
            }
        }
        int t = k-j+1;
        if(t%2==0){
            int[]b = new int[n-t/2];
            for(int i=0;i<j;i++){
                b[i] = a[i];
            }
            for(int i=j;i<j+t/2;i++){
                b[i] = m+1;
            }
            for(int i=j+t/2;i<n-t/2;i++){
                b[i] = a[i+t/2];
            }
            p = Math.min(p,helper(b));
        }
        else{
            for(int q=0;q<=t/2;q++){
                int[]b = new int[j+q];
                int[]c = new int[n-k-1+t/2-q];
                for(int i=0;i<j;i++){
                    b[i] = a[i];
                }
                for(int i=j;i<j+q;i++){
                    b[i] = m+1;
                }
                for(int i=0;i<t/2-q;i++){
                    c[i] = m+1;
                }
                for(int i=t/2-q;i<n-k-1+t/2-q;i++){
                    c[i] = a[i+k+1-t/2+q];
                }
                p = Math.min(p,helper(b)+helper(c)+1);
            }
        }
        return p;
    }
}