首页 > 试题广场 >

栈和排序

[编程题]栈和排序
  • 热度指数：5908 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个从 1 到 n 的排列 P，以及一个空栈。你按顺序将排列中的元素依次入栈，可以在任意时刻选择将栈顶元素出栈并将其加入输出序列。入栈顺序不可改变。

\hspace{15pt}理想情况下，你想得到一个严格从大到小排序的输出序列 n, n-1, \dots,1，但受栈操作限制可能无法实现。当无法完全排序时，请输出**字典序**最大的合法出栈序列。

输入描述:
\hspace{15pt}在一行中输入一个整数 n \left(1 \leqq n \leqq 10^6\right)。 
\hspace{15pt}第二行输入 n 个整数，表示排列 P 中的元素，用空格分隔。保证给出的是一个从 1 到 n 的排列。


输出描述:
\hspace{15pt}输出一行，包含若干整数，表示最终的出栈序列，用空格分隔，结尾不输出多余空格。
示例1

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

入栈顺序和操作示例如下： 
\hspace{8pt}2 入栈； 
\hspace{8pt}1 入栈； 
\hspace{8pt}5 入栈； 
\hspace{8pt}5 出栈； 
\hspace{8pt}3 入栈； 
\hspace{8pt}4 入栈； 
\hspace{8pt}4 出栈； 
\hspace{8pt}3 出栈； 
\hspace{8pt}1 出栈； 
\hspace{8pt}2 出栈。

备注:

算法知识视频讲解
添加回答
C
Regrett头像 Regrett
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int function(char *s) {
    int break_pos = -1;
    int max ;
    int let1 = 1000,let2 = 1000;
    int letTOP = -1,let2TOP = -1;
    char *str = malloc(sizeof(char) * let1);
    char *PUT = malloc(sizeof(char) * let2);
    if(str == NULL || PUT == NULL) {
        printf("配对内存失败！\n");
        free(str);free(PUT);
        return 1;
    }
    int LENG = strlen(PUT);
    int LONG = strlen(s);
    int LONG2 = strlen(str);
    int i = 0;
    int current_pos = 0;
    while(current_pos < LONG) {
        if(letTOP + 1 >= let1) {
        let1 *= 2;
        char *temp = realloc(str,sizeof(char) * let1);
        if(!temp) {
            free(str),free(PUT);
            return 1;
        }
        str = temp;
        }
        if(let2TOP + 1 >= let2) {
            let2 *= 2;
            char *temp = realloc(PUT,sizeof(char) * let2);
            if(!temp) {
                free(str),free(PUT);
                return 1;
            }
            PUT = temp;
        }
        max = s[current_pos];
        for(i = current_pos;i < LONG;i += 1) {
            if(max < s[i]) {
                max = s[i];
            }
        }
        for(i = current_pos;i < LONG;i += 1) {
            if(s[i] != max) {
                str[++letTOP] = s[i];
            }
            if(s[i] == max) {
                PUT[++let2TOP] = s[i];
                break_pos = i;
                break;
            }
        }
        if(break_pos != -1) {
            max = s[break_pos + 1];
            current_pos = break_pos + 1;
            for(i = break_pos + 2;i < LONG;i += 1) {
                if(max < s[i]) {
                    max = s[i] ;
                }
            }
        }
    }
    str[letTOP + 1] = '\0';  
    PUT[let2TOP + 1] = '\0';
    for(i = 0;i < LENG; i += 1)
        printf("%c ",PUT[i]);
    for(i = LONG2 - 1;i >= 0;i -= 1)
        printf("%c ",str[i]);
    free(str);free(PUT);
    return 0;
}
int main() {
    int i;
    int n;
    if(scanf("%d",&n) != 1 || 1 > n || n > 1000000)
        return 1;
    char s[n + 1];
    for(i = 0;i < n;i += 1) {
        scanf(" %c",&s[i]);
    }
    s[n] = '\0';
    function(s);
    return 0;
} //大佬们，为啥运行错误，好像不能解决大数据，怎么处理呀?
发表于 2026-01-27 18:02:55 回复(0)
C
Comeand头像 Comeand

这很贪心了



#include <stdio.h>
#define MAXN 1000005

int stack[MAXN];              //贪心思想；一旦有符合预期的直接带走，然后把预期减小
int p[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }
    int top = -1;
    int max_val = n;
    int i = 0;
    while (i < n || top >= 0) {
        if (i < n) {
            stack[++top] = p[i++];
            // 出栈所有等于当前max_val的元素
            while (top >= 0 && stack[top] == max_val) {
                printf("%d ", stack[top--]);
                max_val--;
            }
        } else {
            // 出栈剩余元素
            printf("%d ", stack[top--]);
        }
    }
    return 0;
}
发表于 2025-11-24 13:50:23 回复(0)
C
123456789201803221944171头像 123456789201803221944171

include <stdio.h>

include <stdlib.h>

typedef struct Stack {
int* base;
int top;
} Stack;
void initstack(Stack* p, int capacity) {
int* s = (int)malloc(sizeof(int) * capacity);
if (!s) exit(1);
p->base = s;
p->top = 0;
}
void push_stack (Stack p, int v) {
p->base[p->top++] = v;

}
void pop_stack(Stack* p) {
p->top--;
}
int top(Stack* p) {
return p->base[p->top - 1];
}

int main() {
int a = 0;
scanf("%d", &a);
int* P = (int*)malloc(sizeof(a) * a) ;
if (!P) exit(1);
for (int i = 0; i < a; i++) {
scanf("%d ", &P[i]);
}
Stack mystack;
int j = 0;
initstack(&mystack, a);
for (int i = 0; i < a; i++) {
while (j < a) {
push_stack(&mystack, P[j++]);
if (top(&mystack) == a - i) {
break;
}
}

    if (i < a) {
        printf("%d ", top(&mystack));
    } else {
        printf("%d\n", top(&mystack));
    }
    pop_stack(&mystack);
}
free(P);
free(mystack.base);
P = mystack.base = NULL;
return 0;

}

int* base;

int top;

} Stack;

void initstack(Stack* p, int capacity) {

int* s = (int*)malloc(sizeof(int) * capacity);

if (!s) exit(1);

p->base = s;

p->top = 0;

}

void push_stack (Stack* p, int v) {

p->base[p->top++] = v;

}

void pop_stack(Stack* p) {

p->top--;

}

int top(Stack* p) {

return p->base[p->top - 1];

}

int main() {

int a = 0;

scanf("%d", &a);

int* P = (int*)malloc(sizeof(a) * a) ;

if (!P) exit(1);

for (int i = 0; i a; i++) {

    scanf("%d ", &P[i]);

}

Stack mystack;

int j = 0;

initstack(&mystack, a);

for (int i = 0; i a; i++) {

    while (j a) {

        push_stack(&mystack, P[j++]);

        if (top(&mystack) == a - i) {

            break;

        }

    }

    if (i a) {

        printf("%d ", top(&mystack));

    } else {

        printf("%d\n", top(&mystack));

    }

    pop_stack(&mystack);

}

free(P);

free(mystack.base);

P = mystack.base = NULL;

return 0;

}

发表于 2025-08-14 11:01:48 回复(0)
提交观点

问题信息

上传者：牛客301599号
难度：
4条回答 4756浏览

热门推荐

通过挑战的用户

查看代码

相关试题

栈和排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号