栈和排序

[编程题]栈和排序

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

给你一个1->n的排列和一个栈，入栈顺序给定

你要在不打乱入栈顺序的情况下，对数组进行从大到小排序

当无法完全排序时，请输出字典序最大的出栈序列

输入描述:

第一行一个数n
第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格

输出描述:

输出一行n个数表示答案，用空格隔开，结尾无空格

示例1

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

2入栈；1入栈；5入栈；5出栈；3入栈；4入栈；4出栈；3出栈；1出栈；2出栈

算法知识视频讲解

C/C++

KBing

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++)
        cin >> v[i];

    vector<int> biggest(n, v[n-1]);
    for(int i = n-2; i >= 0; i--)
        biggest[i] = max(biggest[i+1], v[i]);

    vector<int> ans;
    stack<int> s;

    for(int i = 0; i < n; i++) {
        s.push(v[i]);
        while(!s.empty() && s.top() > biggest[i+1]) {
            ans.push_back(s.top());
            s.pop();
        }
    }
    while(!s.empty()) {
        ans.push_back(s.top());
        s.pop();
    }
    for(auto &num : ans)
        cout << num << " ";
    cout << endl;
    return 0; 
}

发表于 2021-03-29 17:01:36 回复(0)