【刷题-牛客】出栈、入栈的顺序匹配 (代码+动态演示)
💗题目描述 💗:
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<= pushV [i]<=1000
- pushV 的所有数字均不相同
💗解释 : 其实这个题目的意思就是把通常经常遇见的判断题 已知入栈顺序(入栈的同时可以出栈),判断不可能的出栈顺序 ,封装成一个方法,然后我们通过此方法,传入 入栈顺序 和 可能的出栈顺序,方法返回 true 代表 该出栈顺序是可能的, 返回false 代表 该出栈顺序是不可能的 .
解题思路
遍历入栈顺序进行压栈,压栈之后遍历可能的出栈顺序,如果遍历到的元素若与此时栈顶元素相同则表示应该出栈,然后继续后移判断;若不相同则表示此时不用出栈,转而继续进行压栈操作.
接下来我将通过动态图演示具体的过程,同时会将伪代码先写出来
例子 入栈顺序 : 1 2 3 4 5 可能的出栈顺序 : 4 3 5 1 2
动图演示
- 可能出现的bug
我们通过观察伪代码中的while循环语句的条件,我们并没有考虑如果栈为空和 j 下标越界的情况 , 为什么要考虑这两种情况呢 ?
原因 : 我们在需要对这个代码进行测试 , 也就是看这个代码是否满足所有测试用例可能出现的情况.
当入栈顺序和可能的出栈顺序是相反的 : 可能的出栈顺序② : 5 4 3 2 1 入栈顺序 : 1 2 3 4 5
当栈为空的时候,我们就不能再进入while循环的条件语句去执行s.peek()==popV[j]了,所以我们可以在while条件
中增加一个条件 && != s.empty()
当入栈顺序和可能的出栈顺序是相同的 : 可能的出栈顺序③ : 1 2 3 4 5 入栈顺序 : 1 2 3 4 5
此时在while循环中执行完s.pop() 之后,需要继续执行 j++ ,那么 j 就变成了popV.length了. 所以此时我们不能进入while循环的条件语句去执行s.peek() == popV[j] 了,因为此时的 j 会出现下标越界异常,所以我们可以增加一个条件&& j<popV.length
- 继续完善
由于题目要求 0<=pushV.length == popV.length <=1000 那么我们给方法传入的两个数组参数是可能为空的,为了提升代码的健壮性,我们可以可再继续加一个 if 条件语句 <font color=‘red’ return false;`
完整代码
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型 */ public boolean IsPopOrder (int[] pushV, int[] popV) { Stack<Integer> stack = new Stack<>(); int j = 0; if(pushV.length == 0 || popV.length == 0) return false; for (int i = 0; i < pushV.length; i++) { stack.push(pushV[i]); while(j<popV.length&& !stack.empty() && stack.peek().equals(popV[j])){ stack.pop(); j++; } } return stack.empty(); } }
多组测试
- 测试一
- 测试二
- 测试三
- 测试四
求三连!!!
