给定一个堆栈的入栈序列为{ 1, 2, ⋯, n }，出栈序列为{ p 1 ​ , p 2 ​ , ⋯, p n ​ }。如果p 2 ​ =n，则存在多少种不同的出栈序列

根据出栈序列的定义，我们可以发现，如果一个数在出栈序列中的位置比另一个数靠前，那么这个数一定不能在另一个数的上方（也就是先出栈）。

因此，我们可以考虑用贪心的策略来构造出栈序列。具体来说，我们从左到右遍历入栈序列中的每个数，对于每个数，我们都将其入栈，然后尽可能地将栈顶的数出栈，直到栈顶的数等于当前出栈序列中的下一个数。

这样做的正确性可以通过反证法来证明。假设我们按照上述策略得到的出栈序列与给定的出栈序列不同，那么说明在某个位置上，两个序列的数不同。设这个位置是第i个位置，我们考虑两个数的关系：

- 如果第i个位置上的数在给定的出栈序列中在第j个位置上（j>i），那么我们在构造出栈序列时一定会先将第j个位置上的数出栈，因此第i个位置上的数也一定已经出栈了，与假设矛盾。
- 如果第i个位置上的数在给定的出栈序列中在第j个位置上（j<i），那么我们在构造出栈序列时一定会先将第i个位置上的数出栈，然后再将第j个位置上的数出栈，因此第j个位置上的数也一定已经出栈了，与假设矛盾。

因此，我们得到的出栈序列一定与给定的出栈序列相同。

接下来，我们考虑如何计算有多少种不同的出栈序列。我们可以发现，如果p 2 ​ =n，那么n一定会出现在最后一个位置上，因此我们可以将n从栈中取出，然后考虑剩下的入栈序列{ 1, 2, ⋯, n−1 }和出栈序列{ p 1 ​ , p 2 ​ , ⋯, p n−1 ​ }之间的关系。

设f(i,j)表示剩下的入栈序列为{ i, i+1, ⋯, n−1 }，出栈序列为{ j 1 ​ , j 2 ​ , ⋯, j n−i ​ }时，有多少种不同的出栈序列。其中，j 1 ​ 表示出栈序列中第一个数，j 2 ​ 表示出栈序列中第二个数，以此类推。

我们考虑如何计算f(i,j)。根据上述的贪心策略，我们知道，如果某个数在出栈序列中的位置比另一个数靠前，那么这个数一定不能在另一个数的上方。因此，我们可以考虑当前入栈序列中的第一个数x，它只有两种出栈的可能性：

- x先出栈，然后j 1 ​ 出栈，然后f(i+1,j 2 ​ )种情况；
- j 1 ​ 出栈，然后x出栈，然后f(i+1,j 1 ​ )种情况。

因此，f(i,j)的值可以通过上述两种情况的值之和来计算：

f(i,j) = f(i+1,j 2 ​ ) + f(i+1,j 1 ​ )

初始条件为f(n,1)=1，表示入栈序列为{ n }，出栈序列为{ 1 }时只有一种情况。

最终的答案即为f(1,p 1 ​ )。