单调栈

作者: Co_zy | 来源:发表于2018-07-24 19:06 被阅读0次

    单调栈

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

    相关文章

      网友评论

          本文标题:单调栈

          本文链接:https://www.haomeiwen.com/subject/ihvymftx.html