本文转载自微信公众号《程序员千语》，作者程序员千语。转载本文请联系程序员倩语公众号。力扣：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof”GitHub：https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_24_validateStackSequences/Solution.javastackpushandpopsequence》标题描述：输入两个整数序列，第一个序列代表堆栈的push顺序，请判断是否第二个序列是堆栈的弹出序列。假设压入堆栈的所有数字都不相等。比如序列{1,2,3,4,5}是某个栈的入栈序列，序列{4,5,3,2,1}是入栈序列对应的出栈序列，但是{4,3,5,1,2}不能是push序列的pop序列。示例：输入：pushed=[1,2,3,4,5],popped=[4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1),push(2),push(3),push(4),pop()->4,push(5),pop()->5,pop()->3,pop()->2,pop()->1示例2：输入：pushed=[1,2,3,4,5],popped=[4,3,5,1,2]输出：false解释：1不能在2之前弹出。提示：0<=pushed.length==popped.length<=10000<=pushed[i],popped[i]<1000pushed是popped的排列。解题思路：利用栈对元素进行入栈出栈，相等则出栈。如下图所示，给定一个push序列pushed和一个pop序列popped，push/pop操作的顺序（即排列）是唯一确定的。如下图所示，栈的数据操作具有“先进先出”的特点，所以有些出栈顺序无法实现。考虑借用一个辅助栈来模拟push1pop操作的排列。根据模拟是否成功，可以得到结果。推送操作：按照推送顺序执行。出栈操作：每次入栈后，循环判断“栈顶元素=出栈序列当前元素”是否为真，将符合出栈顺序的栈顶元素全部出栈。由于题目规定栈上的所有数字都不相等，所以循环栈中每个元素出栈的可能性是唯一的（如果有重复的数字，则有多个出栈位置）。因此，当遇到“栈顶元素=弹出序列的当前元素”时，应该立即弹出。算法流程：初始化：辅助栈，弹出序列的索引i；push序列的遍历：每个元素记录为num；元素num被压入堆栈；循环出栈：若栈顶元素=出栈序列元素popped[i]，则执行出栈和i++；返回值：如果出栈为?，则本次出栈顺序合法。复杂度分析：时间复杂度O(N)：其中N为推送的列表长度；每个元素最多可以压入和弹出一次，即总共最多进行2N次入栈操作。空间复杂度O(N)：辅助栈最多可以同时存储N个元素。packagecom.nateshao.sword_offer.topic_24_validateStackSequences;importjava.util.Stack;/***@dateCreatedby邵通杰on2021/11/2821:53*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：入栈出栈序列*输入两个整数序列，第一个Sequence表示入栈序列栈的出栈顺序，请判断第二个序列是否为栈的出栈序列。*假设压入堆栈的所有数字都不相等。比如序列{1,2,3,4,5}就是某个栈的入栈序列，*sequence{4,5,3,2,1}就是入栈序列对应的出栈序列，但是{4,3,5,1,2}不能是push序列的pop序列。*https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof*/publicclassSolution{publicstaticvoidmain(String[]args){int[]pushed={1,2,3,4,5};int[]popped={4,5,3,2,1};int[]popped1={4,3,5,1,2};booleanb=validateStackSequences1(pushed,popped);System.out.println("b="+b);//b=truebooleanb1=validateStackSequences2(pushed,popped1);System.out.println("b1="+b1);}/***精选解答**@parampushed*@parampopped*@return*/publicstaticbooleanvalidateStackSequences1(int[]pushed,int[]popped){if(pushed==null||pushed==null)returnfalse;Stack
