题解 | 栈和排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        if (a == null || a.length == 0) {
            return new int[0];
        }

        int n = a.length;

        //构建上帝视角数组：记录每个位置及其之后的最大值
        int[] rightMax = new int[n];
        rightMax[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], a[i]);
        }

        Stack<Integer> stack = new Stack<>();
        int[] result = new int[n];
        int resIndex = 0;

        //模拟入栈和出栈
        for (int i = 0; i < n; i++) {
            // 按顺序入栈
            stack.push(a[i]);

            //如果栈不为空，且 已经没有元素要入栈了(i == n-1) 或者 栈顶元素大于“未来”可能的最大值
            while (!stack.isEmpty() && (i == n - 1 || stack.peek() > rightMax[i + 1])) {
                result[resIndex++] = stack.pop();
            }
        }

        return result;
    }
}