栈和排序

public int[] solve (int[] a) {
        int n=a.length;
        Stack<Integer>stack=new Stack<>();
        int[]dp=new int[n];
        dp[n-1]=a[n-1];
        for(int i=n-2;i>=0;i--)
            dp[i]=Math.max(dp[i+1],a[i]);  //用一个数组记录第i个及之后最大元素
        int[]res=new int[n];
        int j=0;
        for(int i=0;i<n;i++){
            stack.push(a[i]);
            while(!stack.isEmpty()&&i<n-1&&stack.peek()>=dp[i+1]) 
                res[j++]=stack.pop();//如果栈顶元素比后面的都大，那么出栈
        }
        while(!stack.isEmpty()) res[j++]=stack.pop(); //最后在栈中的按顺序弹出
        return res;
    }

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here
        stack<int> s;
        vector<int> res;
        vector<bool> f(aLen + 1, false);
        int now = aLen;
        for(int i = 0; i < aLen; i ++){
            s.push(a[i]);
            f[a[i]] = true;
            while(now > 0 && f[now])now --;
            while(!s.empty() && s.top() > now){
                res.push_back(s.top());
                s.pop();
            }
        }
        return res;
    }
};

import java.util.*;

/**
 * NC115 栈和排序
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // return solution1(a);
        // return solution2(a);
        return solution3(a);
    }

    /**
     * 模拟法: Stack+TreeSet
     * @param a
     * @return
     */
    private int[] solution1(int[] a){
        int n = a.length;

        TreeSet<Integer> treeSet = new TreeSet<>((o1, o2) -> (o2-o1));
        for(int i=n-1; i>=0; i--){
            treeSet.add(a[i]);
            if(a[i] == n){
                break;
            }
        }

        int max = treeSet.pollFirst();

        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num: a){
            stack.push(num);
            treeSet.remove(num);
            if(stack.peek() == max){
                result[i++] = stack.pop();
                while(!stack.isEmpty() && !treeSet.isEmpty() && stack.peek()>treeSet.first()){
                    result[i++] = stack.pop();
                }
                if(!treeSet.isEmpty()){
                    max = treeSet.pollFirst();
                }
            }
        }

        while(!stack.isEmpty()){
            result[i++] = stack.pop();
        }

        return result;
    }

    /**
     * 模拟法: Stack(简化)
     * @param a
     * @return
     */
    private int[] solution2(int[] a){
        int n = a.length;
        // rMax[i]: i右侧最大值(不包括自身)
        int[] rMax = new int[n];
        int max = a[n-1];
        for(int i=n-2; i>=0; i--){
            max = Math.max(max, a[i+1]);
            rMax[i] = max;
        }

        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i=0,j=0; i<n; i++){
            stack.push(a[i]);
            if(stack.peek() == max){
                result[j++] = stack.pop();
                // rMax[n-1]=0 全部弹出
                while(!stack.isEmpty() && stack.peek()>rMax[i]){
                    result[j++] = stack.pop();
                }
                max = rMax[i];
            }
        }

        return result;
    }

    /**
     * 模拟法: Stack(再简化)
     * @param a
     * @return
     */
    private int[] solution3(int[] a){
        int n = a.length;
        // rMax[i]: i右侧最大值(包括自身)
        int[] rMax = new int[n];
        rMax[n-1] = a[n-1];
        for(int i=n-2; i>=0; i--){
            rMax[i] = Math.max(rMax[i+1], a[i]);
        }

        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i=0; i<n; i++){
            while(!stack.isEmpty() && stack.peek()>rMax[i]){
                result[j++] = stack.pop();
            }
            stack.push(a[i]);
        }

        while(!stack.isEmpty()){
            result[j++] = stack.pop();
        }

        return result;
    }
}

class Solution:
    def solve(self , a: List[int]) -> List[int]:
        stack = []
        n = len(a)
        max_val = n
        res = []
        for i in range(n):
            stack.append(a[i])
            while stack and stack[-1] == max_val and i != n-1:
                res.append(stack.pop())
                after_max = max(a[i+1:])
                if stack and stack[-1] > after_max:
                    max_val = stack[-1]
                else:
                    max_val = after_max                    
        while stack:
            res.append(stack.pop())
        return res

from operator import index
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 栈排序
# @param a int整型一维数组 描述入栈顺序
# @return int整型一维数组
#
class Solution:
    def solve(self , a: List[int]) -> List[int]:
        # write code here
        if len(a) == 0&nbs***bsp;len(a) == 1:
            return a

        stack = []
        stack.append(a[0])
        res = []

        # 构建右视图最大表
        right_max = [0 for i in range(len(a))]
        right_max[-1] = a[-1]
        for i in range(len(a)-2, -1, -1):
            right_max[i] = max(a[i], right_max[i + 1])

        index = 1
        while index < len(a):
            if len(stack) == 0:
                stack.append(a[index])
                index += 1
                continue

            # 栈顶大于入栈数，将栈顶加入结果
            if stack[-1] >= right_max[index]:
                res.append(stack[-1])
                stack.pop()
            else:
                stack.append(a[index])
                index += 1

        while len(stack) != 0:
            res.append(stack[-1])
            stack.pop()


        return res

import java.util.*;


public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        //保存要返回的值
        int arr[]=new int[a.length];
        //创建集合保存结果
        ArrayList<Integer> list = new ArrayList<>();
        //创建栈
        Stack<Integer> stack = new Stack<>();
        stack.push(a[0]);
        for (int i = 1; i < a.length; i++) {
            int max = max(a, i);
            //栈顶元素小于后面最大值，就入栈
            if (stack.peek() < max) {
                stack.push(a[i]);
            } else {
            //栈顶元素大于后面最大值，说明已经找到最大的，就出栈
                //循环遍历，直到栈顶比后面最大值还小
            while(!stack.isEmpty()&&stack.peek()>max){
                list.add(stack.pop());
            }
                stack.push(a[i]);
            }
        }
        //将值添加到数组并返回
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        for(int i=0;i<list.size();i++){
            arr[i]=list.get(i);
        }
        return arr;
    }
    public int max(int [] arr, int index) {
        int max = Integer.MIN_VALUE;
        for (int i = index; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
}

#
# 栈排序
# @param a int整型一维数组 描述入栈顺序
# @return int整型一维数组
#
class Solution:
    def solve(self , a ):
        # write code here
        n, stack, dp, res = len(a), [], [0]*len(a), []
        dp[-1] = a[-1] # 记录从第i个元素开始到最后的最大元素
        for i in range(n-2, -1, -1):
            dp[i] = max(dp[i+1], a[i])
        for i in range(n):
            stack.append(a[i])
            while stack and i < n-1 and stack[-1]>=dp[i+1]:
                res.append(stack.pop()) # 如果栈顶元素比后面所有元素都大，则弹出
        while stack:
            res.append(stack.pop())
        return res

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here
        vector<int> res;
        stack<int> aux;
        int i=0;
        aux.push(a[i++]);
         while (aux.size()||i<=aLen){
            if(i==aLen){
                while(aux.size()){
                    res.push_back(aux.top());
                    aux.pop();
                }
                i++;
            }
            else{
                if(aux.size()){
                    int top=aux.top();
                    int next_max=*(std::max_element(a+i,a+aLen));
                    while(top>next_max){
                        aux.pop();

                        res.push_back(top);
                        if(aux.size())
                            top=aux.top();
                        else
                            break;
                    }
                }
                aux.push(a[i++]);
            }
        }
        return res;
    }
};