单调栈
运行时限: 10000 ms 单次运行时限: 10000 ms 内存限制: 32 MB
总提交: 23次 通过: 5次
题目描述
单调栈是一个特殊的栈，它与普通的栈不同的地方在于：当准备把一个元素x从栈顶压栈的时候，如果目前栈顶元素y比x大，那么要将栈顶出栈；直至栈顶元素小于等于x或者栈为空，此时再将x入栈。（可以根据样例理解）
这样最后的栈自底到顶元素就是单调的，所以叫做单调栈。
程序输入说明
第一行一个整数n(n<=100000)，表示待入栈的元素个数
第二行n个整数，表示一次入单调栈的元素
所有输入的元素是不超过10^9的正整数
程序输出说明
将最终状态的单调栈从底到顶按顺序输出
程序输入样例
可见格式 带空格和换行符的格式 带空格和换行符的格式说明
6
3 4 1 5 6 5
程序输出样例
Original Transformed 带空格和换行符的格式说明
1 5 5
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
//int input;
int stack[100000];
int input[100000];
int k;
int top = -1;
int i;
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&input[i]);
}
for(i=0; i<n; i++)
{
if(top == -1)
stack[++top] = input[i];
else if(top!=-1 && stack[top] >input[i])
{
// do
// {
// top--;
// }
// while(stack[top] <= input[i] || top == -1);
// stack[++top] = input[i];
while(1)
{
top--;
if(stack[top] <= input[i] || top == -1)
{
stack[++top] = input[i];
break;
}
}
}
else
stack[++top] = input[i];
}
//printf("top:%d\n",top);
for(i=0; i<=top; i++)
printf("%d ",stack[i]);
//printf("%d %d %d",stack[0],stack[1],stack[2]);
return 0;
}
//3 4 1 5 6 5
