数据结构----依据出栈顺序判断所需的最少栈空间

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 L L, M M M 为当前最大元素，记 S k S_k Sk​ 为第 k k k 步时栈内元素个数, 栈大小的下限为 S a S_a Sa​，记 V k V_k Vk​ 为第 k k k 个元素的值。求解算法如下

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

最后得栈大小下限为 S a = 3 S_a = 3 Sa​=3

2.2 算法分析

2.2.1 算法推导

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

S k + 1 = { S k + ( V k + 1 − M − 1 ) V k + 1 > M S k − 1 V k + 1 < M S_{k+1}=\left\{ \begin{aligned} &S_k + ( V_{k+1} - M - 1) &V_{k+1} > M \\ &S_k - 1 & V_{k+1} < M \end{aligned} \right. Sk+1​={​Sk​+(Vk+1​−M−1)Sk​−1​Vk+1​>MVk+1​<M​

最后可得 S a = M a x ( S 1 , . . . , S L ) + 1 S_a = Max(S_1,..., S_L) + 1 Sa​=Max(S1​,...,SL​)+1, 其中 L L 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