1、要求

给定一个入栈序列和一个出栈序列，判断这个出栈序列是否合法。

例如：

入栈序列：pushV:[1, 2, 3, 4, 5, 6, 7]

出栈序列：popV:[1, 3, 2, 5, 7, 6, 4]

2、实现思路

我们使用栈模拟的方式来做这道题：

  • 使用一个辅助栈来模拟出入栈的过程

  • 用两个指针来遍历出栈序列和入栈序列

    1. 指针 i 用来遍历入栈序列，开始指向1（入栈序列的第一位）。

    2. 指针j用来遍历出栈序列，开始指向1（出栈序列的第一位）。

    3. 对于 1 这个元素，由于 pushV[i] == popV[j]。让 1 入栈后立马出栈就能得到出栈时1的位置。因此我们不管1，直接考虑下个元素（i++，j++）。

    4. 对于 3 这个元素，由于 pushV[i] ！= popV[j]。让 2 入栈后立马出栈显然不合法，所以我们把 2 这个元素入栈后，让 i 继续往后走，一直走到 3 的位置。

    5. 走到 3 的位置后，此时 pushV[i] == popV[j] 。让 3 入栈后立马出栈就能得到 3 的位置，所以我们不管3，直接考虑下个元素（i++，j++）。但是。由于栈中有元素，我们就要考虑栈顶元素是不是出栈序列位置上的元素，如果是，让栈顶弹出，j 指针往后走。直到栈为空或者栈顶元素不是 j 指向的元素。

    6. 重复上述过程，直到 i 指针走到头（i == pushV.size()）。

  • 最后如果辅助栈中元素为空，说明这个出栈序列是合法的。否则说明出栈序列非法。

用这个思路分析上面的例子就是：（我们只要盯着出栈序列元素，想办法让入栈元素出栈入栈后尽可能满足出栈序列元素的位置）

  1. 元素1：出栈，入栈。————>输出：1
  2. 元素3: 2入栈，3入栈，3出栈—————>输出3
  3. 元素2：栈中2出栈————>输出2
  4. 元素5: 4 入栈，5入栈，5出栈————>输出5
  5. 元素:7： 6入栈，7入栈，7出栈————>输出7
  6. 元素6：6出栈————>输出6
  7. 元素4: 4出栈————>输出4
  8. 辅助栈空，故出栈序列合法。

3、代码实现

	bool IsPopOrder(vector<int> pushV,vector<int> popV) {
	    stack<int>s;
	    int i = 0;
	    int j = 0;
	    while(i!=pushV.size())
	    {	
	        if(pushV.at(i)!=popV.at(j))
	        {
	        	s.push(pushV.at(i));
	        	i++;
	        }
	        else
	        {
	        	i++;
	        	j++;
	        	while(!s.empty() && popV.at(j)==s.top())
	        	{
	        		s.pop();
	        		j++;
	        	}
	        }
	    }
	    if(!s.empty()) return false;
	    else return true;
	}

4、案例讲解

接下来看道题目：

alt

输入：

[1,3,2]

返回值：

true

说明：

是上图的后序遍历 ，返回true

4.1 算法思路

  1. 二叉树的中序遍历和后序遍历对应着一种栈的压入、弹出序列，而对于后序遍历从小到大就得到了中序遍历序列。
  2. 我们得到中序遍历序列后，将其作为入栈序列，检查后续遍历是不是一个合法的出栈序列即可（用上面的方法去做）

4.2 代码实现

class Solution {
public:
	bool IsPopOrder(vector<int> pushV,vector<int> popV) {
	    stack<int>s;
	    int i = 0;
	    int j = 0;
	    while(i!=pushV.size())
	    {
	        if(pushV.at(i)!=popV.at(j))
	        {
	        	s.push(pushV.at(i));
	        	i++;
	        }
	        else
	        {
	        	i++;
	        	j++;
	        	while(!s.empty()&&popV.at(j)==s.top())
	        	{
	        		s.pop();
	        		j++;
	        	}
	        }
	    }
	    if(!s.empty()) return false;
	    else return true;
	}
    bool VerifySquenceOfBST(vector<int> sequence) {
    	if(sequence.empty()) return false;
    	vector<int> inOrder(sequence);
    	sort(inOrder.begin(),inOrder.end());
    	return IsPopOrder(inOrder,sequence);
    }
};