进栈出栈问题

进栈出栈问题

zhangheng

January 9, 2020

2195 views

No comments

184 words

算法竞赛

问题描述：
1~N范围内的所有自然数按照从小到大的顺序（1，2，...，N）依次等待进栈。

比如现在N=3:

我们知道有些出栈顺序是合法的，例如{3,2,1}/{1,2,3}等

而有些出栈顺序是不可能出现（非法）的，例如{3,1,2}

现在给出1组出栈顺序，请你判断其是否合法。

输入：

第1行包含1个整数N（1 <= N <= 20），代表元素个数。
第2行包含N的整数，代表出栈顺序，空格隔开。

输出：

如果非法，输出“No”；
如果合法，输出“Yes”，以及在整个入栈/出栈过程中，栈的最大size，空格隔开。
样例输入：

样例1：

4
2 4 3 1

样例2：

4
2 4 1 3

样例输出：
样例1：

Yes 3
*合法，过程中{1,3,4}同时在栈中时size达到最大

样例2：

No

思路：
该题就是考察近栈出栈的理解，该题我们可以用一个洗碗模型来解释：姐姐洗碗，妹妹把姐姐洗过的碗一个一个地放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？
而问题的答案就是卡特兰数：f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-1)*f(0)
其通项：C(2n,n)/(n+1)
但是这个问题考察的n个递增元素依次入栈，所以问题就相对简化了一些。虽然是以次进栈，但是在中途有元素也可以先出栈，所以该题就是要知道不一定所有的元素进栈完后才出栈。所以，我们根据规律得出，对于任何一个元素来说，当它进栈的时候，它下面的元素必然都比它小。因为我们前面所有元素都是按照从小到大的顺序进栈的。因为我们前面所有元素都是按照从小到大的顺序进栈的。而出栈的时候呢，当这个大的元素出栈的时候，后面接着要出栈的元素里只要是原来它下面的元素，就必然一个比一个小。所以，我们也可以概括成这样，对于栈里任何一个出栈的元素来说，生成的序列里它后面所有比它小的元素必然构成一个递减的序列。所以，按照这个规律，我们可以来判断一个给定的序列是否为通过入栈出栈生成的。
代码如下：


   #include<bits/stdc++.h>
   using namespace std;
   bool isRight(vector<int> a)
   {
    //int marked[a.size()];
    for(int i=0;i<a.size();i++)
     {
       //if(marked[i]) continue;
   
      int item=a[i];
      //marked[i]=true;
      for(int j=i+1;j<a.size();j++) 
       {
         //if(marked[j])    continue;
         
         if(a[j]<a[i])//找到比它小的元素，而这些比它小的元素要构成递减
          {
              if(a[j]>item)
                return false;
              else
            {
              item=a[j];//用于和下一个a[j]作比较，来判断是否为递减 
            }
           //marked[j]=true;     
          }
       }
              
    }
    return true;
    }


   int main()
   {
   int n,x,k=1;
   vector<int> a;
   list<int> size; 
   cin>>n;
   for(int i=0;i<n;i++)
    {
        cin>>x;
        a.push_back(x);
    }
    if(isRight(a))
     {
       cout<<"Yes";
       for(int i=0;i<a.size();i++)//用于判断进栈个数最大时的size
     { 
     
      k=1; 
      for(int j=i+1;j<a.size();j++) //就是判断每个数所在的递减数列的最大size
       {
         if(a[j]<a[i])
          {
         k++;          
          }
         size.push_back(k); 
       }
   }
   size.sort();
   cout<<" "<<size.back(); //输出最大的size
     }
    else
       cout<<"No"; 
   
   
       return 0;      
    
   }

进栈出栈问题