输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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. pushV 的所有数字均不相同
[编程题]栈的压入、弹出序列
- 热度指数：770403 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
示例1
输入
[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
示例2
输入
[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
请教一下问题出在哪
public boolean IsPopOrder (int[] pushV, int[] popV) {
Stack<Integer> stack = new Stack<>();
int i, j = 0;
for (i = 0; i < pushV.length; i++) {
if (pushV[i] == popV[j]){
j++;
if (!stack.isEmpty() && stack.peek() == popV[j]){
j++;
stack.pop();
}
} else {
stack.push(pushV[i]);
}
}
for (int k = 0; k < stack.size(); k++) {
if (stack.pop() != popV[j]){
return false;
}
j++;
}
return true;
}
发表于 2024-09-15 11:22:05
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型一维数组
* @param popV int整型一维数组
* @return bool布尔型
*/
public boolean IsPopOrder (int[] pushV, int[] popV) {
// write code here
if(pushV == null || popV == null) {
return false;
}
int len1 = pushV.length;
int len2 = popV.length;
if(len1 != len2) {
return false;
}
Stack<Integer> sta = new Stack<>();
int j = 0;
for(int i = 0; i < len1; i++) {
sta.push(pushV[i]);
while(!sta.isEmpty() && sta.peek() == popV[j]) {
j++;
sta.pop();
}
}
return sta.isEmpty();
}
}
发表于 2023-07-18 11:42:06
回复(0)
public class Solution {
public boolean IsPopOrder(int [] pushA, int [] popA) {
List<Integer> listA = Arrays.stream(pushA).boxed().collect(Collectors.toList());
List<Integer> listB = Arrays.stream(popA).boxed().collect(Collectors.toList());
Stack<Integer> stack = new Stack<>();
int first = listB.get(0);
int index;
for (index = 0; index < listA.size(); index++) {
if (listA.get(index) != first) {
stack.push(listA.get(index));
} else {
break;
}
}
if (index >= listA.size()) return false;
stack.push(listA.get(index));
List<Integer> aList = listA.subList(index + 1, listA.size());
Queue aQueue = new LinkedList();
for (Integer it : aList) {
aQueue.add(it);
}
Queue bQueue = new LinkedList();
for (Integer it : listB) {
bQueue.add(it);
}
return judge(stack, aQueue, bQueue);
}
private boolean judge(Stack<Integer> stack, Queue<Integer> aQueue,
Queue<Integer> bQueue) {
if (stack.isEmpty() && aQueue.isEmpty() && bQueue.isEmpty()) {
return true;
}
if (stack.isEmpty() && !aQueue.isEmpty() && !bQueue.isEmpty()) {
stack.push(aQueue.poll());
return judge(stack, aQueue, bQueue);
}
if (!bQueue.isEmpty() && !stack.isEmpty() &&
Objects.equals(bQueue.peek(), stack.peek())) {
bQueue.poll();
stack.pop();
return judge(stack, aQueue, bQueue);
}
if (!bQueue.isEmpty() && !stack.isEmpty() && bQueue.peek() != stack.peek() &&
!aQueue.isEmpty()) {
stack.push(aQueue.poll());
return judge(stack, aQueue, bQueue);
}
return false;
}
}
发表于 2023-03-09 16:26:01
回复(0)
public boolean IsPopOrder(int [] pushA, int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int popAi = 0;
int pushAi = 0;
//先将首元素进行一个压栈的操作
stack.push(pushA[pushAi++]);
//下面进行循环当两个数组同时遍历完就退出
while (pushAi < pushA.length || popAi < popA.length) {
//因为要stack.peek()所以必须提前判断一下栈是否是空的
//当栈顶元素与popA当前指向的元素相同时就出栈，popAi++
if (!stack.empty() && stack.peek() == popA[popAi]) {
popAi++;
stack.pop();
//当pushA数组没有遍历完的时候则进行压栈操作
} else if (pushAi < pushA.length) {
stack.push(pushA[pushAi++]);
//否则就是不正常情况直接退出循环就行了
} else {
break;
}
}
//判断一下栈是否为空，空的话就返回true
if (stack.empty()) {
return true;
} else {
return false;
}
}
发表于 2022-10-21 17:10:59
回复(0)
import java.util.Stack;
//输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
//假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列
public class Solution {
public boolean IsPopOrder(int [] pushA, int [] popA) {
int i = 0;
int j = 0;
Stack<Integer> stack = new Stack<>();
//模拟判断出栈序列是否合法的过程
//如果想满足出栈序列
//那么就挨个看出栈序列的元素，如果当前栈顶就是这个元素，那就出，否则就只能入栈 直到满足当前栈顶是我想出栈的那个元素
//break:如果入栈序列都走完了，该入栈的元素都入了，没元素可入栈了,却还是不满足栈顶元素等于要出栈的元素 就break
//最后判断:即出栈序列没遍历完 肯定就是false 遍历完 说明确实能这样出栈 返回true
while (true) {
if (!stack.empty() && stack.peek() == popA[j]) {
stack.pop();
j++;
} else {
if (i < pushA.length) {
stack.push(pushA[i]);
i++;
} else {
break;
}
}
}
if (j == popA.length) {
return true;
}
return false;
}
}
发表于 2022-10-20 18:26:09
回复(0)
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA, int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int j = 0;//遍历popA数组
for(int i = 0;i < pushA.length;i++){
stack.push(pushA[i]);
//相同弹出去
//j< popA.length防止j越界
//!stack.empty()防止空栈异常
while(j< popA.length && !stack.empty() && stack.peek(). equals(popA[j]) ){
stack.pop();
j++;
}
}
return stack.empty();
}
}
发表于 2022-09-24 20:51:27
回复(0)
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA, int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int push = 0;
//正常情况下，当前pop的值要么在stack顶端，要么在剩下未push值里
for (int pop = 0; pop < popA.length; pop++) {
//在stack顶就弹出
if (!stack.isEmpty() && stack.peek() == popA[pop]) {
stack.pop();
continue;
}
for (; push < pushA.length; push++) {
//遍历push，如果和pop值相等，跳过，相当于已经push和pop了
if (pushA[push] == popA[pop]) {
push++;
break;
}
//如果不相等，这些值还在需要pop的值前面，全部push进去
if (pushA[push] != popA[pop]) {
stack.push(pushA[push]);
}
}
}
if (stack.isEmpty()) {
return true;
} else {
return false;
}
}
}
发表于 2022-09-09 02:37:52
回复(0)
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
for (int i = 0, j = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (!stack.isEmpty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
发表于 2022-08-17 10:23:59
回复(0)
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack stack = new Stack();
int j=0;
for(int i=0;i<pushA.length;i++) {
stack.push(pushA[i]);
while(stack.isEmpty()==false&&stack.top()==popA[j]){
stack.pop();
j++;
}
}
if(stack.isEmpty()) {
return true;
}
else {
return false;
}
}
}
class Stack{
private Node head;
private int N;
public class Node{
int item;
Node next;
public Node(int item,Node next) {
this.item=item;
this.next=next;
}
}
public Stack() {
head=new Node(-99,null);
N=0;
}
public boolean isEmpty() {
return N==0;
}
public void push(int i) {
Node lastNode = head.next;
Node newNode = new Node(i,null);
head.next=newNode;
newNode.next = lastNode;
N++;
}
public int pop() {
if(head.next==null) {
return -99;
}
Node lastNode = head.next.next;
Node popNode = head.next;
head.next=lastNode;
N--;
return popNode.item;
}
public int top() {
if(head.next==null) {
return -99;
}
else {
return head.next.item;
}
}
}
发表于 2022-07-02 21:22:17
回复(0)
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA==null){
return false;
}
if(pushA.length!=popA.length){
return false;
}
int index=0;
Stack<Integer> stack=new Stack<>();
//压入操作
for(int i=0;i<pushA.length;i++){
if(pushA[i]!=popA[index]){
stack.push(pushA[i]);
}else{
index++;
//判断前面一个是否一样
while(!stack.isEmpty()){
int val=stack.peek();
if(val==popA[index]){
index++;
stack.pop();
}else{
break;
}
}
}
}
//弹出操作
while(!stack.isEmpty()){
int val=stack.pop();
if(val==popA[index]){
index++;
}else{
return false;
}
}
return true;
}
}
发表于 2022-07-02 20:28:04
回复(0)
import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0 ;
for(int i = 0 ; i < pushA.length; i++){
stack.push(pushA[i]);//现将目标数组入栈
while(!stack.empty()&&stack.peek() == popA[j]){
//假如相同就出栈
stack.pop();
j++;
//popA++
}
}
if(stack.empty()){
//假如栈为空那么就说明相同
return true;
}
return false;
}
} import java.util.*;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0 ;
for(int i = 0 ; i < pushA.length; i++){
stack.push(pushA[i]);//现将目标数组入栈
while(!stack.empty()&&stack.peek() == popA[j]){
//假如相同就出栈
stack.pop();
j++;
//popA++
}
}
if(stack.empty()){
//假如栈为空那么就说明相同
return true;
}
return false;
}
}
发表于 2022-06-22 18:04:55
回复(0)
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if (popA == null || pushA == null || popA.length == 0 || pushA.length == 0) {
return false;
}
Stack<Integer> stack = new Stack<>();
int i = 0, j = 0;
for (; i < pushA.length; i++) {
stack.push(pushA[i]);
while (!stack.isEmpty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
发表于 2022-05-26 11:47:49
回复(0)
给出栈数组popA设一个指针，入栈过程中遇到值相等则出栈，并将指针移到下一位，不相等则继续入栈。最后pushA读完后，将剩余元素依次出栈，和出栈数组popA当前指针开始一一比较，都相同则可以是弹出序列
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {Stack s=new Stack();
int length=pushA.length;
int j=0;
for(int i=0;i<length;i++){
s.push(pushA[i]);
while(s.size()!=0){
if((int)s.peek()==popA[j]){
s.pop();
j++;
}else{
break;
}
}
}
while(s.size()!=0){
if((int)s.pop()!=popA[j])
return false;
j++;
}
return true;
}
}
发表于 2022-05-14 20:49:28
回复(0)
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length==0||popA.length==0){
return false;
}
Stack<Integer> stack=new Stack<>();
int j=0;
for(int i=0;i<pushA.length;i++){
int val=pushA[i];
stack.push(val);
while(!stack.empty()&&j<popA.length&&stack.peek()==popA[j]){
stack.pop();
j++;
}
}
return stack.empty();
}
}
发表于 2022-05-12 14:24:59
回复(0)
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA, int [] popA) {
if (pushA == null || popA == null)return false;
Stack<Integer> stack = new Stack<Integer>();
int indexpop = 0;
int indexpush = 0;
while (indexpop < pushA.length) {
while (stack.isEmpty() || indexpush < pushA.length &&
stack.peek() != popA[indexpop]) {
stack.push(pushA[indexpush]);
indexpush = indexpush + 1;//如果栈顶不是右边的index，就继续压栈
}
if (stack.pop() != popA[indexpop]) {
return false;//如果栈顶不能把右边index取出来，false
}
indexpop = indexpop + 1;//一轮取出一个右边index
}
if (stack.isEmpty())return true;
else return false;
}
}
发表于 2022-03-29 20:45:55
回复(0)
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack();
int pushIndex = 0, popIndex = 0;
while(pushIndex < pushA.length){
stack.push(pushA[pushIndex++]);
while(popIndex<popA.length && !stack.isEmpty() && stack.peek()==popA[popIndex]){
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
发表于 2022-01-29 17:30:22
回复(0)
import java.util.ArrayList;
import java.util.*;
public class Solution {
Stack<Integer> stack = new Stack<>();
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0) return true;
int l = pushA.length;
int posPush = 0,posPop = 0;
while(posPop < l){
if(stack.isEmpty() || stack.peek() != popA[posPop]){
while(posPush < l && pushA[posPush] != popA[posPop]){
stack.push(pushA[posPush]);
posPush++;
}
if(posPush == l) return false;
posPush++;
}
else{
stack.pop();
}
posPop++;
}
return true;
}
}
import java.util.*;
public class Solution {
Stack<Integer> stack = new Stack<>();
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0) return true;
int l = pushA.length;
int posPush = 0,posPop = 0;
while(posPop < l){
if(stack.isEmpty() || stack.peek() != popA[posPop]){
while(posPush < l && pushA[posPush] != popA[posPop]){
stack.push(pushA[posPush]);
posPush++;
}
if(posPush == l) return false;
posPush++;
}
else{
stack.pop();
}
posPop++;
}
return true;
}
}
发表于 2022-01-23 14:35:26
回复(0)
问题信息
难度：
263条回答
4005收藏
176059浏览
通过挑战的用户
查看代码-
2023-03-11 00:50:32 -
2023-03-10 20:38:13
-
2023-03-07 14:56:03 -
2023-03-07 11:04:02
-
2023-03-04 15:16:26
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { if(pushV.size() == 0) return false; vector<int> stack; for(int i = 0,j = 0 ;i < pushV.size();){ stack.push_back(pushV[i++]); while(j < popV.size() && stack.back() == popV[j]){ stack.pop_back(); j++; } } return stack.empty(); } };