题解 | #栈和排序#

import java.util.*;


public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        Stack<Integer> s = new Stack();//定义一个栈用来存储数据
        int n = a.length;
        int[] res = new int[n];//用来返回结果
        int cnt = 0;
        boolean[] vis = new boolean[n+10];//用来标记哪个数字出现过
        for(int i =0; i < a.length;i++){//遍历数组
            s.push(a[i]);//压入栈
            vis[a[i]] = true;//压入一个数就把对应的数字标记为true
            while(n > 0 && vis[n]) n--;//检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
            while(!s.empty() && n <= s.peek()){
                //然后将栈中&gt;=n的元素出栈
                res[cnt++] = s.pop();
            }
        }
        //如果栈没为空就按照栈中原样直接出栈
        while(!s.empty()){
            res[cnt++] = s.pop();
        }
        return res;
    }
}