首页 > 试题广场 >

栈和排序

[编程题]栈和排序
  • 热度指数:9511 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给你一个 1 到 n 的排列和一个栈,并按照排列顺序入栈

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

排列:指 1 到 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]
dp问题,要求字典序最大,首先,第一个弹出的数应该是整个数组的最大值,那么最大值左边的数按顺序入栈, 最大值入栈后pop, 为第一个输出值;
然后第二个数选哪个呢?如果是在最大值左边的,也就是栈里的数,它输出必须按照栈顶弹出顺序,我们无法改变, 如果是在最大值右边的,我们应该选择的是最大值右边的序列中的最大值mr[i+1][0], 
mr[i][0]为a[i......n-1]中的最大值, mr[i][1\为最大值所在坐标index.

左右两边选择哪个哪个呢,那当然是哪边大选哪个,那就需要比较st.top()和mr[i+1][0],如果st.top()大,就输出,一直pop(),直到st.top()<mr[i+1][0], 接下来再一直push到mr[i+1][1].


class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here
        int j=0, n=aLen;
        vector<vector<int>> mr(n, vector<int>(2, 0));
        int Max = INT_MIN;
    
        for(int i=n-1; i>=0; i--) {
            if(Max<a[i]) {
               Max = a[i];
               j = i;
            }
            mr[i][0] = Max;
            mr[i][1] = j;
        }
        stack<int> st;
        vector<int> ans;
        for(int i=0; i<n; i++) {
            st.push(a[i]);
            if(i==mr[i][1]) {
                ans.push_back(st.top());
                st.pop();
                while(!st.empty() && i<n-1 && st.top()>mr[i+1][0]) {
                    ans.push_back(st.top());
                    st.pop();
                }
            }
        }
        while(!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        return ans;
    }
};


发表于 2020-08-06 18:44:15 回复(1)
每日吐槽牛客编程题:***一样的题目描述
发表于 2021-08-08 09:40:00 回复(0)
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)
思路:保证当前弹出的数比之后要入栈的数大即可
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)
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;
    }
};

发表于 2021-09-23 20:35:30 回复(1)
什么鬼,O(n)这也超时
发表于 2021-08-10 11:57:00 回复(2)
发布前先看看自己能读懂题吗???
发表于 2024-03-24 14:55:26 回复(0)
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)
您提交的代码无法完成编译
main.cc:21:46: error: too few arguments to function call, expected 2, have 1
vector ret12 = solution.solve( a);
~~~~~~~~~~~~~~ ^
./solution.h:10:17: note: 'solve' declared here
vector solve(int* a, int aLen) {
^
1 error generated.

????
发表于 2023-02-08 19:11:15 回复(0)
菜鸡表示看不懂题

发表于 2022-09-17 19:47:01 回复(0)
class Solution {
public:
    vector<int> solve(int* a, int aLen) {
        vector<int> ans; //vector保存的是顺序容器,即从小到大
        set<int> right;    // 右集合
        for (int i = 0; i < aLen; i++) {    // 先将全部元素都插入集合
            right.insert(a[i]);
        }
        stack<int> stk;
        for (int i = 0; i < aLen; i++) {
            // 只要a[i]后面都没有比它大的数, 就出栈
            if (right.size()) {    // 集合不为空
                auto it = right.end();
                --it;    // 找到最大值
                if (*it == a[i]) ans.push_back(a[i]);    // 后面没有比a[i]大的数, 加入出栈序列
                else stk.push(a[i]);    // 后面后比a[i]大的数, a[i]入栈
                it = right.find(a[i]);
                right.erase(it);    // 从集合中删除a[i]
                while (!stk.empty() && !right.empty()) {    // 不断检查栈顶
                    auto it = right.end();
                    --it;
                    if (*it < stk.top()) {
                        ans.push_back(stk.top());
                        stk.pop();
                    }
                    else break;
                }
            }
            else ans.push_back(a[i]);    // 集合为空,直接加入出栈序列
        }

        // 若栈非空, 则依次出栈并加入到出栈序列中
        while (stk.size()) {
            ans.push_back(stk.top());
            stk.pop();
        }

        return ans;
    }
};
发表于 2021-12-17 19:44:22 回复(2)
java
import java.util.*;


public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        // write code here
        int n = a.length;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] maxArr = new int[n];
        // 倒叙记录每个位置元素后面出现的最大元素
        maxArr[n-1] = Integer.MIN_VALUE;
        int tempMax = Integer.MIN_VALUE;
        for(int i=a.length-2;i>=0;i--){
            maxArr[i] = Math.max(a[i+1], maxArr[i+1]);
        }
        
        for(int i=0;i<n;i++){
            System.out.print(maxArr[i]+"  ");
        }
        int[] ans = new int[n];
        int index = 0;
        for(int i=0;i<n;i++){
            if(a[i] > maxArr[i]){  // 当前入栈元素大于将要入栈的元素
                ans[index++] = a[i];
                while(!stack.isEmpty() && stack.peek()>maxArr[i]){
                    ans[index++] = stack.pop();
                }
            }else{
                stack.push(a[i]);
            }
        }
        while(!stack.isEmpty()){
            ans[index++] = stack.pop();
        }
        return ans;
    }
}


发表于 2021-12-05 16:42:53 回复(0)
#
# 栈排序
# @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

发表于 2021-06-24 14:49:05 回复(0)
class Solution:
    def solve(self , a ):
        # write code here
        n = len(a)
        if n == 0:
            return []
        max_right = [0]*n 
        max_right[n-1] = -1
        maxo = a[n-1]
        for i in range(n-2,-1,-1):
            max_right[i] = maxo
            if a[i] > maxo:
                maxo = a[i]
        queue = []
        ans = []
        for i in range(n):
            queue.append(a[i])
            while len(queue)-1 >=0 and queue[len(queue)-1] >= max_right[i]:
                ans.append(queue.pop())
                
        while len(queue)!=0:
            ans.append(queue.pop())
        return ans

发表于 2021-06-02 16:03:25 回复(0)
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;
    }
};
编辑于 2021-04-21 20:22:46 回复(0)
    8/9 通过率 有漏洞 求优化
 public int[] solve(int[] a) {
        if (a == null || a.length == 0) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int length = a.length;
        for (int i = 0; i < length; i++) {
            int num = a[i];
            if (stack.isEmpty()) {
                stack.add(num);
            } else {
                Integer peek = stack.peek();
                int index = i + 1;
                int max = 0;
                while (index < length) {
                    if (a[index] > max) {
                        max = a[index];
                    }
                    index++;
                }
                if (peek <= num && num <= max) {
                    stack.add(num);
                } else if (peek >= num && num >= max) {
                    stack.add(num);
                } else if (peek <= num && num >= max) {
                    list.add(num);
                } else if (peek >= num && num <= max) {
                    if (peek <= max) {
                        stack.add(num);
                    } else {
                        Integer pop = stack.pop();
                        list.add(pop);
                        while (!stack.isEmpty() && stack.peek() >= num && stack.peek() >= max) {
                            Integer pop1 = stack.pop();
                            list.add(pop1);
                        }
                        stack.add(num);
                    }
                }
            }
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i);
        }
        return ints;
    }
发表于 2021-04-10 22:57:16 回复(0)
    public static int[] solve(int[] a) {
        if (a == null || a.length == 0) {
            return a;
        }
        int index = 0, n = a.length;
        int Max = Integer.MIN_VALUE;
        int[][] maxarr = new int[n][2];
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] > Max) {
                Max = a[i];
                index = i;
            }
            maxarr[i][0] = Max;
            maxarr[i][1] = index;
        }
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            stack.push(a[i]);
            if (maxarr[i][1] == i) {
                list.add(stack.pop());
                while (!stack.isEmpty() && i < n - 1 && stack.peek() > maxarr[i + 1][0]) {
                    list.add(stack.pop());
                }
            }
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        int[] res = new int[a.length];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

发表于 2020-11-04 17:00:33 回复(1)
代码超时,有大佬能优化吗?
public static int[] solve (int[] a) {
        // write code here
        Stack<Integer> stat=new Stack<Integer>();
        int len=a.length;
        int rmax[]=new int[len+1];
        rmax[len]=0;
        int[] result=new int[len];
        if(len==0){
            return result;
        }
        int p=0;
        for(int i=len-1;i>=0;i--){
            rmax[i]=Integer.max(a[i],rmax[i+1]);
        }
        for(int j=0;j<a.length;j++){
            while(!stat.isEmpty()&&stat.peek()>=rmax[j]){
                result[p++]=stat.pop();
            }
            stat.push(a[j]);
        }
        while(!stat.isEmpty()){
            result[p++]=stat.pop();
        }
        return result;
    }

发表于 2020-10-04 15:18:45 回复(1)