京东 2020校招 笔试第一题：合唱队 AC:100
时间限制： 3000MS
内存限制： 589824KB
#java求职##笔试题目#
内存限制： 589824KB
题目描述：
合唱队的N名学生站成一排且从左到右编号为1到N，其中编号为i的学生身高为Hi。现在将这些学生分成若干组（同一组的学生编号连续），并让每组学生从左到右按身高从低到高进行排列，使得最后所有学生同样满足从左到右身高从低到高（中间位置可以等高），那么最多能将这些学生分成多少组？
输入描述
第一行包含一个整数N，1≤N≤105。
第二行包含N个空格隔开的整数H1到HN，1≤Hi≤109。
输出描述
输出能分成的最多组数。
解析：一个正确的分组应该要保证该分组内的最大值要小于等于下一个分组的最小值，这样形成一个递归，保证某个分组的最小值大于等于前面所有分组的最大值，该分组的最大值小于等于后面所有分组的最小值，这样既可以保证分组数最多，也可以保证这些分组排序后组成的整个序列是有序的。为了达到前面的目的，我们可以判断该数是不是可以重新分组的依据是若该数前面所有的数（包括该数）的最大值小于等于该数后面所有的数（不包括该数）的最小值，就表明该数可以作为一个新的分组。代码如下
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] arr=new int[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } int count =0; int[] preMax=new int[n]; preMax[0]=arr[0]; int[] aftMin=new int[n]; aftMin[n-1]=Integer.MAX_VALUE; //求取该数后面所有的数（不包括该数）的最小值 for(int i=n-2;i>=0;i--) { aftMin[i]=Math.min(arr[i+1],aftMin[i+1]); } //求取该数前面所有的数（包括该数）的最大值 for(int i=1;i<n;i++) { preMax[i]=Math.max(preMax[i-1],arr[i]); } for(int i=0;i<n;i++) { if(preMax[i]<=aftMin[i]) { count++; } } System.out.println(count); } }
