题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
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
|
import Foundation
class For22Solution {
func isStackPushAndPop(_ pushStack: [Int],_ popStack: [Int]) -> Bool {
//辅助栈，取弹出序列的首位，等于栈顶就弹出。
var stack = [Int]()
var pushIndex = 0
var popIndex = 0
while popIndex <= popStack.count - 1 {
let popFirst = popStack[popIndex]
while stack.last != popFirst {
if pushIndex > pushStack.count - 1 {
return false
}
stack.append(pushStack[pushIndex])
pushIndex += 1
}
if stack.last == popFirst {
stack.popLast()
popIndex += 1
}
}
return true
}
}
|
算法思想：如果第二个序列中当前要判断的元素刚好与栈顶元素相等，则直接pop出来，如果不等，则将第一个序列的后面还没有入栈的元素入栈，直到将与之相等的元素入栈为止，如果第一个序列的所有的元素都入栈了，还没有找到与之相等的元素，则说明第二个序列不是第一个序列的弹出序列，
github地址：https://github.com/cubegao/LeetCode
