每天一道剑指offer-栈的压入、弹出序列

乔戈里

发布于 2019-09-17 16:49:58

2560

发布于 2019-09-17 16:49:58

文章被收录于专栏：Java那些事Java那些事

前言

今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

昨天的题解

题目

每天一道剑指offer-栈的压入、弹出序列来源：牛客网对应专题

题目详述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

题目详解

思路

一个弹出序列，一个压栈序列，弹出序列中的数，比如第一个弹出的数，肯定是在压栈过程中弹出来的，所以在这里新建一个栈stack,如果压栈序列中要压入的数和弹出序列当前的数不一样（说明没找到），那么压栈序列继续压，直到压栈序列中找到了和弹出序列当前下标值相等的数，那么弹出序列的下标值就+1,。
结束条件就是弹出序列的下标值可以到达序列的末尾。

代码

import java.util.*;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length != popA.length) 
            return false;
        Stack<Integer> stack1 = new Stack<>();//栈记录压栈
        int j = 1;
        stack1.push(pushA[0]);//栈中先压入push压栈序列的第一个数
        for(int i=0;i<popA.length;i++)
        {
            while(j < pushA.length && stack1.peek() != popA[i])
            {//如果栈顶的数和弹出序列不一样，就一直压栈，因为必须是从栈顶弹出的！
                stack1.push(pushA[j]);
                j++;
            }
            if(j >= pushA.length && stack1.peek() != popA[i])
                return false;//如果j已经到达压栈序列的末尾，但是栈顶的数还是和弹出序列当前的数不一致
                             //说明没有这个序列
            stack1.pop();
        }
        return true;
    }
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-12-11，如有侵权请联系 cloudcommunity@tencent.com 删除

github