栈的压入,弹出序列
栈的压入、弹出序列
http://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
栈的压入,弹出序列
(完全是利用规律解决的问题,没有使用奇淫技巧)
首先我们去观察规律:
先从popA中拿到第一个弹出的元素,再从pushA中拿到第一个弹出的元素,并记录在pushA中的push_index
那么拿到元素以后,我们如何去判定接下来的元素是否合法呢?分两种情况考虑
- 如果popA中拿到的第二个弹出元素的pop_index是大于push_index
这个情况就无所谓了,重新更新push_index的位置,然后pop_index++(到第三个弹出元素的位置)
- 如果popA中拿到的第二个弹出元素的pop_index是小于push_index
这个情况略复杂,因为栈其实是单向的,也就是“连续的”,那么我们如果pop_index<push_index,那么一定是 紧挨着前一个弹出的元素的
- 如果popA中拿到的第二个弹出元素的pop_index是大于push_index
剩下的步骤和第二步一样了,一直循环,一直到pop_index == popA.size 就好了
PS:有个注意点,就是第二步所说的紧挨着前一个弹出的元素的,这个并不意味着index是相邻的,因此是每次找pushA中找到一个相应的栈的元素的时候,也就应该将这个位置设成一个标志(我设的是-1),最后用来判断是不是“相邻”
举个例子 {1,2,3,4,5} {3,5,4,2,1}
- pop_index:0 push_index:2
- pop_index:1 push_index:4
- pop_index:2 push_index:3
=> 这里要注意了 3 被弹出了,所以四相邻的是2,不是index相邻的3,写代码的时候需要判断这一点 - pop_index:3 push_index:1
- pop_index:4 push_index:0
public boolean IsPopOrder(int [] pushA,int [] popA) { int push_index = 0 ; // 在压栈数组中的index int pop_index = 0 ; // 在弹栈数组中的index boolean flag = false ; if (pushA.length == 0){ // 判断是0的情况 return false ; } if (pushA.length == 1){ // 判断是1的情况 if (pushA[0] == popA[0]){ return true ; } return false ; } for (int i=0;i< pushA.length;i++){ // 当栈的数据大于1的情况 if (pushA[i] == popA[pop_index]){ push_index = i ; pushA[i] = -1 ; pop_index++ ; break; } } while (true) { for (int i = 0; i < pushA.length; i++) { if (i > push_index && pushA[i] == popA[pop_index]) { //情况一: 第二个弹出的元素的位置比原push_index大 push_index = i; pushA[i] = -1; pop_index++; flag = true; break; } else if (i < push_index && pushA[i] == popA[pop_index]) {//情况二: 第二个弹出的元素的位置比原push_index小 for (int j = i + 1; j < push_index; j++) { // 判断相邻的特殊情况 if (pushA[j] != -1) { return false; } } push_index = i; pushA[i] = -1; pop_index++; flag = true; } } if (flag == false) { //预防死循环 return false; } if (pop_index == pushA.length - 1) { //满足条件直接return return true; } flag = false; } }