单调栈

单调栈

运行时限: 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