31.md

栈的压入、弹出序列

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。 1.0<=pushV.length == popV.length <=1000 2.-1000<=pushV[i]<=1000 3.popV 的所有数字均在 pushV里面出现过 4.pushV 的所有数字均不相同

示例

输入：[1,2,3,4,5],[4,5,3,2,1] 返回值：true 说明：可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop(), 这样的顺序得到[4,5,3,2,1]这个序列，返回true

输入：[1,2,3,4,5],[4,3,5,1,2] 返回值：false 说明：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

思路

• 首先注意不是一定全push完后再pop，两个操作可以交叉执行
• 直接模拟，因为弹出之前的值都会先入栈，所以用个栈来辅助

实现

package main

// 栈的压入、弹出序列
func main() {
	pushV := []int{1, 2, 3, 4, 5}
	popV := []int{4, 5, 3, 2, 1}
	IsPopOrder(pushV, popV)
}

func IsPopOrder(pushV []int, popV []int) bool {
	temp := make([]int, 0)
	i := 0
	j := 0
	all := len(pushV)
	for {
		if i >= all {
			break
		}
		if pushV[i] != popV[j] {
			temp = append(temp, pushV[i])
			i++
		} else {
			// 说明这个元素是放入栈中立马弹出
			i++
			j++
			for {
				// 然后检查popV[j]与栈顶元素是否相等
				if len(temp) == 0 || temp[len(temp)-1] != popV[j] {
					break
				}
				// 如果相等弹出临时栈顶元素
				temp = temp[:len(temp)-1]
				j++
			}
		}
	}
	if len(temp) == 0 {
		return true
	} else {
		return false
	}
}