京东笔试第一题合唱团渣渣思路
合唱团题目,感觉是最朴实的思路,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); } }