给定一个最大容量为 m 的堆栈，将 n 个数字按 1, 2, 3, ..., n 的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 m=5、n=7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

### 回答1：
对于给定的堆栈容量m和n个数字，不可能得到的数字序列包括：
1. 序列中的数字数量大于m，因为堆栈只能容纳m个数字。
2. 序列中出现了数字n+1或更大的数字，因为只有1到n的数字入栈。
3. 序列中出现了重复的数字，因为每个数字只入栈一次。

### 回答2：
这道题目其实比较经典，被称为“堆栈的排列问题”，它有一个著名的结论：如果一个长度为n的序列不能按1,2,...,n的顺序入栈和出栈，则这个序列一定包含长度不小于3的递减子序列。

证明思路如下：

假设一个长度为n的序列，不能按1,2,...,n的顺序入栈和出栈。我们通过反证法来说明它一定包含长度不小于3的递减子序列。

假设这个序列没有长度不小于3的递减子序列，那么它的所有子序列都是递增的。考虑一个入栈出栈的过程，由于入栈时必须满足先入后出的顺序，所以这个序列中必须有一个位置i，它之前的数都已经进栈并出栈了，否则就无法满足先入后出的规则。设这个位置为k，即第k个数是最后一个进栈的数。

由于序列中没有长度不小于3的递减子序列，所以第k-1个数不能大于第k个数，否则它们就构成了一个长度为2的递减子序列。同理，第k-2个数也不能大于第k个数，否则它们就构成了一个长度为2的递减子序列。依次类推，第i+1个数不能大于第k个数，否则它们就构成了一个长度为2的递减子序列。综上，第i+1到k-1这段区间内的所有数都比第k个数大。

现在考虑第i个数。由于第i个数比第i+1到k-1这段区间内的所有数都小，所以它必然在第k个数之前进栈，并在第k个数之后才出栈。这就导致了一个矛盾，因为第i到k-1这段区间内的数都已经进栈并出栈了，如果此时第i个数进栈，那么第i到k-1这段区间内的数无法出栈，因为它们已经出栈过了，所以第i个数一定在第k个数之前出栈了。同理，我们可以发现第i-1个数也在第k个数之前出栈了。依次类推，我们可以得到第1个数也在第k个数之前出栈了。这就说明序列可以按1,2,...,n的顺序出栈，并与我们的假设相矛盾。

综上所述，如果一个长度为n的序列不能按1,2,...,n的顺序入栈和出栈，则这个序列一定包含长度不小于3的递减子序列。所以我们可以根据这个结论得到哪些数字序列是不可能得到的。

### 回答3：
这是一道经典的算法题，也被称为“出栈序列”问题。首先，我们需要了解一下堆栈的性质：后入先出。当一个数字 i 进入堆栈时，所有比它小的数字都必须先于它出栈。因此，我们可以通过模拟出栈过程，判断哪些序列是不可能得到的。

假设我们要判断的序列为 a[1], a[2], ..., a[n]，其中 a[1] 是第一个出栈的数字。我们用一个栈 s 来模拟出栈过程，同时用一个指针 i 来指向下一个要出栈的数字，初始值为 1。我们依次遍历序列中的每一个数字，如下所示：

1. 如果 s 为空或者 s 的栈顶元素不等于 a[i]，则将 a[i] 入栈，i 递增。
2. 如果 s 的栈顶元素等于 a[i]，则将栈顶元素出栈，i 递增。
3. 重复步骤 1 和步骤 2，直到序列中的所有数字都遍历完毕。

如果最终栈 s 为空，则序列是可行的；否则，序列是不可行的。因为如果最终栈 s 不为空，说明还有一些数字没有出栈，它们一定比栈顶元素大，而这违反了出栈的规则。

举个例子，对于堆栈最大容量为 5，序列为 3, 2, 1, 5, 4，我们按照上述方法模拟出栈过程：

- 3 进栈；
- 2 进栈；
- 1 进栈；
- 1 出栈，5 进栈；
- 2 出栈，4 进栈；
- 3 出栈；
- 4 出栈；
- 5 出栈。

最终栈 s 为空，序列是可行的。

回到本题，假设堆栈最大容量为 m，我们可以分别枚举每一个数字 k，将 1 到 k 这些数字按顺序入栈。在每次入栈之后，我们模拟出栈过程判断序列是否可行。如果序列不可行，说明加入数字 k 时堆栈已满，那么就不存在可行的出栈序列。

这个算法的时间复杂度为 O(nm^2)，其中 n 为数字的个数，m 为堆栈最大容量。实际上，我们可以使用动态规划优化这个算法，将时间复杂度降至 O(nm)。具体做法可以参考下面的链接，这里不再赘述。

参考链接：https://www.acwing.com/blog/content/2771/