NC115：栈和排序

读入数据：第i个数出栈满足字典序最大,一定是i+1到n中最大的一个数
用一个数组maxs存i-n之间最大的数
按照读入顺序入栈,如果当前入栈第i个数字比将要入栈的剩余元素都要大 那么这个元素出栈
因为让入栈的第i个元素，比将要入栈的i+1到n的元素都大时出栈,总能保证字典序最大

public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        int n=a.length;
        int[] maxs=new int[n];
        int max=Integer.MIN_VALUE;

        //找出i到n中最大的那个值
        for (int i = n-1; i>=0; i--) {
            max=Math.max(max,a[i]);
            maxs[i]=max;
        }

        Stack<Integer>stack=new Stack<>();
        ArrayList<Integer>list=new ArrayList<>();

        for (int i = 0; i <n; i++) {
            stack.push(a[i]);
            while(!stack.isEmpty() && i<n-1 && stack.peek()>maxs[i+1] ){
                list.add(stack.pop());
            }
        }

        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }

        int[] res=new int[n];
        for (int i = 0; i < res.length; i++) {
            res[i]=list.get(i);
        }
        return res;
    }
}

代码2：

public int[] solve (int[] a) {
        // write code here
        int n=a.length;
        int[] maxs=new int[n+1];
        int max=Integer.MIN_VALUE;

        //找出i到n中最大的那个值
        for (int i = n-1; i>=0; i--) {
            max=Math.max(max,a[i]);
            maxs[i]=max;
        }
        maxs[n]=Integer.MIN_VALUE;

        Stack<Integer>stack=new Stack<>();
        ArrayList<Integer>list=new ArrayList<>();

       //如果当前入栈的值 大于i+1到n之间的最大值 那么出栈
       //maxs[i+1]最后一定为0,所有栈内元素可以全部出栈
        for (int i = 0; i <n; i++) {
            stack.push(a[i]);
            while(!stack.isEmpty() && stack.peek()>maxs[i+1] ){
                list.add(stack.pop());
            }
        }

        int[] res=new int[n];
        for (int i = 0; i < res.length; i++) {
            res[i]=list.get(i);
        }
        return res;
    }