题解 | #栈和排序#

import java.util.*;
public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        Stack<Integer> st = new Stack<Integer>();
        int index = 0;
        // 记录当前出现的连续的最大值数组段中的最小值
        // 1 2 * 4 5,代表在数组中1 2 4 5 已经出现，curmax = 4
        int curmax = a.length;
        // 用来记录每个数值是否出现过
        boolean[] vis = new boolean[a.length+1];
        int[] res = new int[a.length];
        for(int i = 0; i < a.length; i++){
            st.push(a[i]);
            vis[a[i]] = true;
            // 查找现在已经出现了的较大值中的最小值
            // 字典序最大，肯定是先弹出最大的一位数值
            // 看看最大的数值是否已经出现，即是否已经入栈
            // 没有入栈的话，就向后遍历直到最大值已经入栈
            // 已经入栈的话，就查找从最大值开始，持续往前查找直到找到未入栈的数值
            // 最终curmax存储的是当前已经入栈的连续的较大值中的最小值
            while(curmax>0 && vis[curmax]==true) curmax--;
            // 只要栈不为空并且栈顶元素大于该curmax值，就代表该元素可以被弹出
            while(!st.isEmpty() && st.peek()>=curmax){
                res[index++] = st.pop();
            }
        }
        // 最终栈中的剩余元素，直接依次弹出追加到数组末尾即可
        while(!st.empty()){
            res[index++] = st.pop();
        }
        return res;
    }
}