4.3 举例让抽象问题具体化

和上一节画图的方法一样，我们也可以借助举例模拟的方法来思考分析复杂的问题。当一眼看不出问题中隐藏的规律的时候，我们可以试着用一两个具体的例子模拟操作的过程，这样说不定就能通过具体的例子找到抽象的规律。比如面试题31“栈的压入、弹出序列”，很多人不能立即找到栈的压入和弹出规律。这时我们可以仔细分析一两个序列，一步一步模拟压入、弹出的操作，并从中总结出隐含的规律。面试题33“二叉搜索树的后序遍历序列”也类似，我们同样可以通过一两个具体的序列找到后序遍历的规律。

具体的例子也可以帮助我们向面试官解释算法思路。算法通常是很抽象的，用语言不容易表述得很清楚，我们可以考虑举一两个具体的例子，告诉面试官我们的算法是怎么一步步处理这个例子的。例如，在面试题30“包含min函数的栈”中，我们可以举例模拟压栈和弹出几个数字，分析每次操作之后数据栈、辅助栈和最小值各是什么。这样解释之后，面试官就能很清晰地理解我们的思路，同时他也会觉得我们有很好的沟通能力，能把复杂的问题用很简单的方式说清楚。

具体的例子还能帮助我们确保代码的质量。在面试中写完代码之后，应该先检查一遍，确保没有问题再交给面试官。怎么检查呢？我们可以运行几个测试用例。在分析问题的时候采用的例子就是测试用例。我们可以把这些例子当作测试用例，在心里模拟运行，看每一步操作之后的结果和我们预期的是不是一致。如果每一步的结果都和事先预计的一致，那我们就能确保代码的正确性了。

面试题30：包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。

看到这个问题，我们的第一反应可能是每次压入一个新元素进栈时，将栈里的所有元素排序，让最小的元素位于栈顶，这样就能在O(1)时间内得到最小元素了。但这种思路不能保证最后压入栈的元素能够最先出栈，因此这个数据结构已经不是栈了。

我们接着想到在栈里添加一个成员变量存放最小的元素。每次压入一个新元素进栈的时候，如果该元素比当前最小的元素还要小，则更新最小元素。面试官听到这种思路之后就会问：如果当前最小的元素被弹出栈了，那么如何得到下一个最小的元素呢？

分析到这里我们发现，仅仅添加一个成员变量存放最小元素是不够的，也就是说当最小元素被弹出栈的时候，我们希望能够得到次小元素。因此，在压入这个最小元素之前，我们要把次小元素保存起来。

是不是可以把每次的最小元素（之前的最小元素和新压入栈的元素两者的较小值）都保存起来放到另外一个辅助栈里呢？我们不妨举几个例子来分析一下把元素压入或者弹出栈的过程，如表4.1所示。

首先往空的数据栈里压入数字3，显然现在3是最小值，我们也把这个最小值压入辅助栈。接下来往数据栈里压入数字4。由于4大于之前的最小值，因此我们仍然往辅助栈里压入数字3。第三步继续往数据栈里压入数字2。由于2小于之前的最小值3，因此我们把最小值更新为2，并把2压入辅助栈。同样，当压入数字1时，也要更新最小值，并把新的最小值1压入辅助栈。

表4.1 栈内压入3,4,2,1之后接连两次弹出栈顶数字再压入0时，数据栈、辅助栈和最小值的状态

步 骤 操 作 数 据 栈 辅 助 栈 最 小 值

1 压入3 3 3 3

2 压入4 3, 4 3, 3 3

3 压入2 3, 4, 2 3, 3, 2 2

4 压入1 3, 4, 2, 1 3, 3, 2, 1 1

5 弹出 3, 4, 2 3, 3, 2 2

6 弹出 3, 4 3, 3 3

7 压入0 3, 4, 0 3, 3, 0 0

从表4.1中可以看出，如果每次都把最小元素压入辅助栈，那么就能保证辅助栈的栈顶一直都是最小元素。当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小值。比如在第四步之后，栈内的最小元素是1。当第五步在数据栈内弹出1后，我们把辅助栈的栈顶弹出，辅助栈的栈顶元素2就是新的最小元素。接下来继续弹出数据栈和辅助栈的栈顶之后，数据栈还剩下3、4两个数字，3是最小值。此时位于辅助栈的栈顶数字正好也是3，的确是最小值。这说明我们的思路是正确的。

当我们想清楚上述过程之后，就可以写代码了。下面是3个关键函数push、pop和min的参考代码。在代码中，m_data是数据栈，而m_min是辅助栈。

template <typename T> void StackWithMin<T>::push(const T& value)

{

m_data.push(value);

if(m_min.size() == 0 || value < m_min.top())

m_min.push(value);

else

m_min.push(m_min.top());

}

template <typename T> void StackWithMin<T>::pop()

{

assert(m_data.size() > 0 && m_min.size() > 0);

m_data.pop();

m_min.pop();

}

template <typename T> const T& StackWithMin<T>::min() const

{

assert(m_data.size() > 0 && m_min.size() > 0);

return m_min.top();

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/30_ MinInStack

测试用例：

新压入栈的数字比之前的最小值大。

新压入栈的数字比之前的最小值小。

弹出栈的数字不是最小元素。

弹出栈的数字是最小元素。

本题考点：

考查应聘者分析复杂问题的思维能力。在面试的时候，很多应聘者都止步于添加一个变量保存最小元素的思路。其实只要举个例子，多做几次入栈、出栈的操作就能看出问题，并想到也要把最小元素用另外的辅助栈保存。当我们面对一个抽象复杂的问题的时候，可以用几个具体的例子来找出规律。找到规律之后再解决问题，就容易多了。

考查应聘者对栈的理解。

面试题31：栈的压入、弹出序列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列{1,2,3,4,5}是某栈的压栈序列，序列{4,5,3,2,1}是该压栈序列对应的一个弹出序列，但{4,3,5,1,2}就不可能是该压栈序列的弹出序列。

解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。

以弹出序列{4,5,3,2,1}为例分析压栈和弹出的过程。第一个希望被弹出的数字是4，因此4需要先压入辅助栈。压入栈的顺序由压栈序列确定，也就是在把4压入栈之前，数字1,2,3都需要先压入栈。此时栈里包含4个数字，分别是1,2,3,4，其中4位于栈顶。把4弹出栈后，剩下的3个数字是1、2和3。接下来希望被弹出的数字是5，由于它不是栈顶数字，因此我们接着在第一个序列中把4以后的数字压入辅助栈，直到压入数字5。这时候5位于栈顶，就可以被弹出来了。接下来希望被弹出的3个数字依次是3、2和1。由于每次操作前它们都位于栈顶，因此直接弹出即可。表4.2总结了本例中入栈和出栈的步骤。

表4.2 压栈序列为{1,2,3,4,5}、弹出序列为{4,5,3,2,1}对应的压栈和弹出过程

步 骤 操 作 栈 弹出数字 步 骤 操 作 栈 弹出数字

1 压入1 1 6 压入5 1, 2, 3, 5

2 压入2 1, 2 7 弹出 1, 2, 3 5

3 压入3 1, 2, 3 8 弹出 1, 2 3

4 压入4 1, 2, 3, 4 9 弹出 1 2

5 弹出 1, 2, 3 4 10 弹出 1

接下来再分析弹出序列{4,3,5,1,2}。第一个弹出的数字4的情况和前面一样。把4弹出之后，3位于栈顶，可以直接弹出。接下来希望弹出的数字是5，由于5不是栈顶数字，到压栈序列里把没有压栈的数字压入辅助栈，直至遇到数字5。把数字5压入栈之后，5就位于栈顶了，可以弹出。此时栈内有两个数字1和2，其中2位于栈顶。由于接下来需要弹出的数字是1，但1不在栈顶，我们需要从压栈序列中尚未压入栈的数字中去搜索这个数字。但此时压栈序列中的所有数字都已经压入栈了，所以该序列不是序列{1,2,3,4,5}对应的弹出序列。表4.3总结了这个例子中压栈和弹出的过程。

表4.3 一个压入顺序为{1,2,3,4,5}的栈没有一个弹出序列为{4,3,5,1,2}

步 骤 操 作 栈 弹出数字 步 骤 操 作 栈 弹出数字

1 压入1 1 6 弹出 1, 2 3

2 压入2 1, 2 7 压入5 1, 2, 5

3 压入3 1, 2, 3 8 弹出 1, 2 5

4 压入4 1, 2, 3, 4 下一个弹出的是1，但1不在栈顶，压栈序列的数字都已入栈。操作无法继续

5 弹出 1, 2, 3 4

总结上述入栈、出栈的过程，我们可以找到判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；如果所有数字都压入栈后仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

形成了清晰的思路之后，我们就可以动手写代码了。下面是一段参考代码：

bool IsPopOrder(const int* pPush, const int* pPop, int nLength)

{

bool bPossible = false;

if(pPush != nullptr && pPop != nullptr && nLength > 0)

{

const int* pNextPush = pPush;

const int* pNextPop = pPop;

std::stack<int>stackData;

while(pNextPop - pPop < nLength)

{

while(stackData.empty() || stackData.top() != *pNextPop)

{

if(pNextPush - pPush == nLength)

break;

stackData.push(*pNextPush);

pNextPush ++;

}

if(stackData.top() != *pNextPop)

break;

stackData.pop();

pNextPop ++;

}

if(stackData.empty() && pNextPop - pPop == nLength)

bPossible = true;

}

return bPossible;

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/31_ StackPushPopOrder

测试用例：

功能测试（输入的两个数组含有多个数字或者只有一个数字；第二个数组是或者不是第一个数组表示的压入序列对应的栈的弹出序列）。

特殊输入测试（输入两个nullptr指针）。

本题考点：

考查应聘者分析复杂问题的能力。刚听到这道面试题的时候，很多人可能都没有思路。这时候可以通过举一两个例子，一步步分析压栈、弹出的过程，从中找出规律。

考查应聘者对栈的理解。

面试题32：从上到下打印二叉树

题目一：不分行从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如，输入图4.6中的二叉树，则依次打印出8,6,10,5,7,9,11。二叉树节点的定义如下：

struct BinaryTreeNode

{

int m_nValue;

BinaryTreeNode* m_pLeft;

BinaryTreeNode* m_pRight;

};

这道题实质是考查树的遍历算法，只是这种遍历不是我们熟悉的前序、中序或者后序遍历。由于我们不太熟悉这种按层遍历的方法，可能一下子也想不清楚遍历的过程。那面试的时候怎么办呢？我们不妨先分析一下打印图4.6中的二叉树的过程。

因为按层打印的顺序决定应该先打印根节点，所以我们从树的根节点开始分析。为了接下来能够打印值为8的节点的两个子节点，我们应该在遍历到该节点时把值为6和10的两个节点保存到一个容器里，现在容器内就有两个节点了。按照从左到右打印的要求，我们先取出值为6的节点。打印出值6之后，把它的值分别为5和7的两个节点放入数据容器。此时数据容器中有3个节点，值分别为10、5和7。接下来我们从数据容器中取出值为10的节点。注意到值为10的节点比值为5和7的节点先放入容器，此时又比这两个节点先取出，这就是我们通常所说的先入先出，因此不难看出这个数据容器应该是一个队列。由于值为5、7、9、11的节点都没有子节点，因此只要依次打印即可。整个打印过程如表4.4所示。

图4.6 一棵二叉树，从上到下按层打印的顺序为8,6,10,5,7,9,11

表4.4 按层打印图4.6中的二叉树的过程

步 骤 操 作 队 列

1 打印节点8 节点6、节点10

2 打印节点6 节点10、节点5、节点7

3 打印节点10 节点5、节点7、节点9、节点11

4 打印节点5 节点7、节点9、节点11

5 打印节点7 节点9、节点11

6 打印节点9 节点11

7 打印节点11

通过上面具体例子的分析，我们可以找到从上到下打印二叉树的规律：每次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的节点，重复前面的打印操作，直至队列中所有的节点都被打印出来。

既然我们已经确定数据容器是一个队列了，现在的问题就是如何实现队列。实际上我们无须自己动手实现，因为STL已经为我们实现了一个很好的deque（两端都可以进出的队列）。下面是用deque实现的参考代码：

void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot)

{

if(!pTreeRoot)

return;

std::deque<BinaryTreeNode *> dequeTreeNode;

dequeTreeNode.push_back(pTreeRoot);

while(dequeTreeNode.size())

{

BinaryTreeNode *pNode = dequeTreeNode.front();

dequeTreeNode.pop_front();

printf("%d ", pNode->m_nValue);

if(pNode->m_pLeft)

dequeTreeNode.push_back(pNode->m_pLeft);

if(pNode->m_pRight)

dequeTreeNode.push_back(pNode->m_pRight);

}

}

源代码：

本题完整的源代码：

http