题目地址：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
题目示例
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
解题思路
辅助栈：考虑利用一个辅助栈sk模拟压入或者弹出操作的排列，根据是否模拟成功，即可得到结果。核心思路是若栈顶元素sk.top()等于弹出序列的当前元素popped[i]，则执行出栈操作。当然，入栈操作是按照压栈序列的顺序执行，而出栈操作是，每次入栈后，循环判断sk.top()==popped[i]是否满足，若满足，则将符合弹出序列顺序的栈顶元素全部弹出。
规律型：口诀“向后随便找，不可向前跳”。遍历popped序列，对里面出现的每个数字到pushed序列中查找，我们将找到的位置在pushed序列中置为-1，然后在pushed中以此位置为界，popped序列中的下一个元素可以出现在我们标记的元素后面，即置为-1的元素位置后面，不管后面有多少元素，但如果出现在标记为-1的位置前面，则不能跳过未访问过的数字，即不能跳过未置为-1的位置的元素，以序列pushed=[1,2,3,4,5]和popped=[4,5,3,1,2]为例说明，首先，遍历popped序列，对其中的第一个元素4在pushed序列中查找，将找到的位置置为-1，得到新的序列pushed=[1,2,3,-1,5]，然后，对popped序列中的第二个元素5查找，可以发现元素5出现在pushed序列中置为-1的元素4后面，所以，可以得出结论，元素5是可以匹配的，初始化序列pushed=[1,2,3,-1,-1]，继续对popped序列中的元素3判断，依旧满足口诀要求，即元素3也是可以匹配成功的，再次初始化序列pushed=[1,2,-1,-1,-1]，接下来，对对popped序列中的元素1判断，发现元素1出现在标记为-1的位置前面，即若想得到元素1，则必须跳过pushed序列中的元素2，不满足要求，所以不能匹配成功。
程序源码
辅助栈
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { if(pushed.size() == 0) return true; if(popped.empty()) return pushed.empty(); stack<int> sk; int cnt = 0; for(int i = 0; i < pushed.size(); i++) //for(int m:pusher){sk.push(num);} { sk.push(pushed[i]); while(!sk.empty() && sk.top() == popped[cnt] && cnt < popped.size()) { sk.pop(); cnt++; } } return sk.empty(); } };
找规律
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { if(pushed.size() == 0) return true; if(popped.empty()) return pushed.empty(); int popped_index = 0, pushed_index = 0; while(popped_index < popped.size()) { bool is_found = false; while(pushed_index < pushed.size()) { if(popped[popped_index] == pushed[pushed_index]) { is_found = true; break; } pushed_index++; } if(is_found == false) return false; pushed[pushed_index--] = -1; while(pushed_index >= 0) { if(pushed[pushed_index] != -1) break; pushed_index--; } if(pushed_index == -1) pushed_index = 0; //元素push并被pop情况 popped_index++; } return true;
参考文章