问题背景
Algorithm 4th (Robert Sedgewick, Kevin Wayne) 一书中有这样一道习题:
1.3.46 Forbidden triple for stack generability. Prove that a permutation can be gener- ated by a stack (as in the previous question) if and only if it has no forbidden triple (a, b, c) such that a < b < c with c first, a second, and b third (possibly with other intervening integers between c and a and between a and b).
翻译成中文,可以理解为:请证明:如果一个栈的出栈顺序合法,当且仅当不存在这样的 forbidden triple:在序列中编号 c 后有编号 a、b,其中 c和a, a和b可以有间隔,而且 a < b < c。 查看全文