栈和排序

[编程题]栈和排序

热度指数：9614 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个 1 到 n 的排列和一个栈，并按照排列顺序入栈

你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列

排列：指 1 到 n 每个数字出现且仅出现一次

数据范围： $1 \le n \le 5 \times 10^4$ ，排列中的值都满足 $1 \le val \le n$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

[2,1,5,3,4]

输出

[5,4,3,1,2]

说明

操作       栈     结果
2 入栈；[2]       []
1 入栈；[2\1]     []
5 入栈；[2\1\5]   []
5 出栈；[2\1]     [5]
3 入栈；[2\1\3]   [5]
4 入栈；[2\1\3\4] [5]
4 出栈；[2\1\3]   [5,4]
3 出栈；[2\1]     [5,4,3]
1 出栈；[2]       [5,4,3,1]
2 出栈；[]        [5,4,3,1,2]

示例2

输入

[1,2,3,4,5]

输出

[5,4,3,2,1]

算法知识视频讲解

Java

牛客825478369号

思路：保证当前弹出的数比之后要入栈的数大即可

import java.util.*;

public class Solution {
    public int[] solve (int[] a) {
        int[] rMax = new int[a.length]; // 当前位置之后的最大值（包括当前位置)
        rMax[a.length - 1] = a[a.length - 1];
        for (int i = a.length - 2; i >= 0 ; i--) {
            rMax[i] = Math.max(rMax[i + 1], a[i]);
        }
        int index = 0;
        int[] res = new int[a.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            while (!stack.isEmpty() && stack.peek() > rMax[i]) { // 若栈顶比右侧大，则弹出
                res[index++] = stack.pop();
            }
            stack.push(a[i]);
        }
        while (!stack.isEmpty()) {
            res[index++] = stack.pop();
        }
        return res;
    }
}

发表于 2023-07-18 14:23:00 回复(0)

Java

梁山教父

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;
    }
}

发表于 2023-05-17 09:50:33 回复(0)

Java

莫里Mori

什么鬼，O(n)这也超时

发表于 2021-08-10 11:57:00 回复(2)

Java

花落梦里

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;
    }

发表于 2021-03-31 14:56:55 回复(0)