1 问题描述

问题: 若元素 a,b,c,d,e,f,g 顺序进栈，且出栈顺序是 b,d,c,f,e,a,g 则栈的容量至少是_____

答案：3

2 解法描述与分析

2.1 解法描述

记 1,2,3,4,5,6… 分别对应 a,b,c,d,e,f…, 记序列长度为 $L$, $M$ 为当前最大元素，记$S_k$ 为第 $k$ 步时栈内元素个数, 栈大小的下限为 $S_a$，记 $V_k$ 为第 $k$ 个元素的值。求解算法如下

对问题有如下的执行过程
step 1: b,d,c,f,e,a,g $\to$ 2,4,3,6,5,1,7
执行完 step 1 之后有如下表的执行步，表中已经把 step 2–step 4 合并

最后得栈大小下限为 $S_a=3$

2.2 算法分析

2.2.1 算法推导

首先栈的大小的下限 $S_a\ge 1$，栈的大小可以通过确定栈中元素最多时来确定，而栈中元素的个数是动态变化的，这有点像湖，水流流入湖中类似于入栈，水从湖中流出，类似于出栈，而确定湖水最高的水平面则类似于确定栈最多元素时的大小。通过确定入栈元素个数和出栈元素个数，便可以确定栈中元素最多时的个数。当元素进入之后立即弹出，一个栈空间就够了，当不立即弹出时，则需要更多的栈空间。如果第k步时栈的中元素的个数为 $S_k$ , 出栈的最大元素为 $M$, 则由 $V_{k+1}$ 与 $M$ 的大小关系便可以确定入栈元素的个数：若 $V_{k+1}>M$ 则处于 $V_{k+1}$ 与 $M$ 之间的元素一定被会压入栈中，$V_{k+1}$ 本身入栈后立即弹出，则此时栈的大小 $S_k+(V_{k+1}-M-1)$，若 $V_{k+1}<M$ 则说明$V_{k+1}$ 是从栈中弹出的且没有入栈操作，此时 $S_k-1$. 由此可得到如下递推关系

$$S_{k+1}=\{\begin{array}{rlr}& S_k+(V_{k+1}-M-1)& V_{k+1}>M\\ & S_k-1& V_{k+1}<M\end{array}$$

最后可得$S_a=Max(S_1,...,S_L)+1$, 其中$L$ 为数列的大小，之所以要加1，是立即入栈出栈的元素也需要一个空间。

2.2.2 算法复杂性分析

时间复杂性 O(n), 空间复杂性 O(1).

3 算法的程序实现

3.1 python 实现

def find_stack_needed_size(in_stack_list, out_stack_list):
    item_dict = {v:i+1 for i,v in enumerate(in_stack_list)}
    S_k,S_a = 0,1
    M = 0
    k = 1
    for item in out_stack_list:
        if item_dict[item] > M:
            S_k = S_k + (item_dict[item] - M - 1)
            M = item_dict[item]
            if S_k + 1 > S_a: S_a = S_k + 1
        else:
            S_k = S_k - 1
        print('k={0}  M={1} S_{0}={2} S_a={3}'.format(k, M, S_k, S_a))
        k += 1
    return S_a

测试：

In : find_stack_needed_size(['a','b','c','d','e','f','g'],['b','d','c','f','e','a','g'])
k=1  M=2 S_1=1 S_a=2
k=2  M=4 S_2=2 S_a=3
k=3  M=4 S_3=1 S_a=3
k=4  M=6 S_4=2 S_a=3
k=5  M=6 S_5=1 S_a=3
k=6  M=6 S_6=0 S_a=3
k=7  M=7 S_7=0 S_a=3
Out: 3