评论详情-牛客网

第一题思路：先对数组排序，然后遍历一遍，统计每个数字在排序树组中第一次出现的位置（数组元素重复时这个下标会出错），遍历结果记录在index数组中，最后对index数组一遍遍历，用maxIndex保存当前最大的index，maxIndex表示当前数组中应当分为一组的最大下标，在i<maxIndex的过程中需要不断更新maxIndex，直到maxIndex等于遍历的位置i时，说明一个合法的子数组遍历完成。

例子：

nums[] = {2,1,6,3,5,4},得到的index[] = {1, 0, 5, 2, 4, 3},第一个合法子数组应该到i=1的位置，第二个合法数组应该到i=5的位置。

AC只有64%，因为这种做法无法处理有重复数字的情况。

import java.util.ArrayList;

import java.util.Scanner;

public class JD1 {
/*
* 2 2
3 1
1 4
* */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer> nums = new ArrayList<>();
        int[] origin = new int[n];
        int[] index = new int[n];
        for(int i=0;i<n;i++) {
            int cur = scanner.nextInt();
            origin[i] = cur;
            nums.add(cur);
        }
        nums.sort((o1,o2)->o1-o2);
        for(int i=0;i<n;i++) {
            index[i] = nums.indexOf(origin[i]);
        }
        int maxIndex = 0;
        int count = 0;
        for(int i=0;i<n;i++) {
            //if(maxIndex==index[i]) maxIndex+=1;
            maxIndex = Math.max(maxIndex, index[i]);
            if(maxIndex == i) count++;
        }
        System.out.println(count);
    }
}