母猪佩七：算法和研发发错卷子了吧?

***星人：白卷的在哪里？

handsome_a...：笔试的时候没写好,后来完善了一下(没有验证,不保证正确)。 思路是单调栈,栈中存放每一组的最大值。 如果当前元素比栈顶元素大,也就是当前元素可以自己分成一组,讲当前元素入栈。 如果当前元素比栈顶元素小,但是比栈中第二个大元素大,那么当前元素和栈顶元素可以分成一组,则不做处理即可。 如果当前元素小于栈中前两个元素，则先保存栈顶元素,讲栈中比当前元素大的都出栈,最后再将刚才保存的栈顶元素入站。最终栈中有几个元素,就可以分几组。 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long a[] = new long[n]; for(int i=0;i<n;i++){ a[i] = sc.nextLong(); } int top = -1; long [] st= new long[n]; st[++top] = a[0]; for(int i=1;i<n;i++){ // 顶部元素 long tmp = st[top]; if(a[i]>=tmp){ st[++top] = a[i]; }else if(!(top>0&&a[i]>=st[top-1])){ while(top>=0&&st[top]>a[i]) { top--; } st[++top] = tmp; } } System.out.println(top+1); }