京东笔试第一题合唱团渣渣思路
合唱团题目，感觉是最朴实的思路，AC91%
思路：
分组的依据是： 某个组内的最大值 要小于后面所有数
用一个指针curr_index记录当前组的末尾位置，一个max记录当前组的最大值
遍历一遍数组，对每个数，如果它后面所有的数都比它大，则分组数+1； 如果遇到一个比它小的数，则将这个数记为curr_index
时间复杂度：最坏 O(n^2)
/*
* 后一组的最小值 要大于前一组的最大值
*/
public class JD1 {
public static void toInt(String[] arg, int[] nums) {
for(int i=0;i<arg.length;i++) {
nums[i] = Integer.parseInt(arg[i]);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int num = Integer.parseInt(in.nextLine());
if(num == 0) {
System.out.println(0);
return;
}
String arg1 = in.nextLine();
int[] h = new int[arg1.split(" ").length];
toInt(arg1.split(" "), h);
int max = h[0], curr_index = 0, ans = 0;
while(curr_index < h.length) {
int curr = max; //记录每个分组中的最大值
int next = curr_index+1; //记录每个分组的末尾位置
while(next < h.length && h[next] >= curr) {
max = Math.max(max, h[next]);
next++;
}
if(next == num) { //后面的数全都比它大
++curr_index; //自己分成一组
++ans;
if(curr_index < num) max = h[curr_index];
}else {
curr_index = next; //遇到比它小的数，从这个小数开始继续找
//if(curr_index)
}
}
System.out.println(ans);
}
} 
曼伦商贸公司福利 164人发布
