题解 | #栈和排序#

import java.util.*;


public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        
        // 定义一个整型变量，用于存放数组 a 的长度
        int len = a.length;
        
        // 定义一个整型数组，用于存放当前位置上，它的右边序列上比它大的数字
        int[] max = new int[len];
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> arrayList = new ArrayList<>();
        
        // 初始化
        max[len - 1] = a[len - 1];
        int maxValue = a[len - 1];
        
        for (int i = len - 2; i > -1; i--) {
            maxValue = Math.max(maxValue, a[i]);
            max[i] = maxValue;
        }
        for (int i = 0; i < len; i++) {
            if (a[i] == max[i]) {
                while (!stack.isEmpty()) {
                    int top = stack.pop();
                    if (top > a[i]) {
                        arrayList.add(top);
                    }
                    else {
                        stack.push(top);
                        break;
                    }
                }
                arrayList.add(a[i]);
            }
            else {
                while (!stack.isEmpty()) {
                    int top = stack.pop();
                    if (top > a[i] && top > max[i]) {
                        arrayList.add(top);
                    }
                    else {
                        stack.push(top);
                        break;
                    }
                }
                stack.push(a[i]);
            }
        }
        while (!stack.isEmpty()) {
            arrayList.add(stack.pop());
        }
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }
}