题解《剑指offer》No.31

题目链接

题目大意

就是给出两个序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可以为该栈的弹出顺序。

解题思路

这道题和PAT甲级的一道题目特别相似,刚好是去年差不多这个时候做过,但是当时想了很久。。书上给出的代码感觉看起来非常的繁琐,不好阅读,我也是看了牛客网上讨论区的题解才做出来的,在这里记录一下。

总的思路大家都知道是模拟过程,但是我一开始想的非常繁琐,不知道怎么停止循环,卡在那里了。牛客网大神给出的非常简单:

还是模拟,从压入序列的起始位置一直向后顺延到末尾即可退出。

每次都是将一个元素压入到辅助栈中去,接着又是一个循环,这个循环将和弹出序列相等的那个部分弹出(如果不满足一个,那么就会跳过,下一轮接着压入一个元素到辅助栈中去),直到有了和当前弹出序列相等的进入栈才会开始这个循环。完全没有复杂的判断。

最后,我们返回辅助栈是否为空,为空,那么表示完全满足。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
/**
* 1 2 3 4 5
* 4 5 3 2 1
* 4 3 5 1 2
* */

bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if (0 == pushV.size() || 0 == popV.size())
return false;
vector <int> v;
int i = 0, j = 0;
while (i < pushV.size())
{
v.push_back(pushV.at(i++));
while (j < popV.size() && v.back() == popV.at(j))
{
++j;
v.pop_back();
}
}
return v.empty();
}
};

int main () {
vector <int> pushV;
vector <int> popV;
for (int i = 1; i < 6; ++i) pushV.push_back(i);
popV.push_back(4);
popV.push_back(5);
popV.push_back(3);
popV.push_back(2);
popV.push_back(1);
// for (int i = 0; i < 5; ++i) cout << pushV[i] << '\t';
// cout << endl;
// for (int i = 0; i < 5; ++i) cout << popV[i] << '\t';
auto solve = new Solution();
cout << solve -> IsPopOrder(pushV, popV) << endl;
}
文章作者: Yeoman Li
文章链接: https://yeomanli.github.io/2019/05/13/题解《剑指offer》No.31/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yeoman's Blog