题解 | #栈的压入、弹出序列#

栈的压入、弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106

package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param pushV int整型一维数组
 * @param popV int整型一维数组
 * @return bool布尔型
 */
// 判断两个序列是否符合入栈出栈的次序,我们就可以用一个栈来模拟
// 对于入栈序列,只要栈为空,序列肯定要依次入栈
// 那什么时候出来呢?自然是遇到一个元素等于当前的出栈序列的元素,那我们就放弃入栈,让它先出来
func IsPopOrder(pushV []int, popV []int) bool {
	// write code here
	// 辅助栈
	var stack []int
	// 入辅助栈的下标
	j := 0
	for i := 0; i < len(pushV); i++ {
		// 辅助栈为空或者辅助栈顶不等于出栈数组
		for j < len(pushV) && (len(stack) == 0 || stack[len(stack)-1] != popV[i]) {
			stack = append(stack, pushV[j])
			j++
		}

		// 辅助栈顶等于出栈数组
		if stack[len(stack)-1] == popV[i] {
			stack = stack[:len(stack)-1]
		} else {
			// 不匹配
			return false
		}
	}

	return true
}

全部评论

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务