东莞网站排名优化公司,手机app制作网站用什么软件,做网站全过程,闸北微信网站建设题目
输入两个整数序列#xff0c;第一个序列表示栈的压入顺序#xff0c;请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如#xff0c;序列 {1,2,3,4,5} 是某栈的压栈序列#xff0c;序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列#xf…题目
输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 {1,2,3,4,5} 是某栈的压栈序列序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例 1 输入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 的排列。 解题思路 1.题目要求我们判断栈的弹出顺序是否是所给两个整数序列对于这道题我们需要设置一个辅助栈来帮助我们。还需要一个变量k来指向我们的出栈元素方便我们读取。 2.举个例子pushed [1,2,3,4,5], popped [4,5,3,2,1] 我们先按入栈顺序入栈第一个元素1 然后判断stack当前的栈顶元素是否等于k指向的出栈顺序的元素若不等于我们就继续入栈 再次判断stack当前的栈顶元素是否等于k指向的出栈顺序的元素不等于我们继续入栈 stack当前的栈顶元素依旧不等于k指向的出栈顺序的元素我们继续入栈 此时我们可以看到 stack当前的栈顶元素等于k指向的出栈顺序的元素我们就将Stack的栈顶元素出栈并将 k 后移。 这时 stack当前的栈顶元素不等于k指向的出栈顺序的元素我们继续按照入栈顺序继续入栈 再次将 stack当前的栈顶元素与k指向的出栈顺序的元素进行判断发现两者相等我们就将栈顶元素进行出栈并且将k后移 出栈 出栈 出栈 此时我们发现stack栈空了那就证明所给的出栈顺序是正确的。 3.本体的主要思想就是我们需要查看栈顶元素是否与出栈顺序所对应的元素相等若相等就出栈若不等就继续按照入栈顺序入栈如果所有的操作结束后栈为空就证明所给顺序正确否则就代表所给顺序有误。 代码实现
class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {//判断所给序列是否为空if(pushed null || pushed.length 0){return true;}//设置一个辅助栈StackInteger stack new Stack();int k 0;for(int i 0; i pushed.length; i){stack.push(pushed[i]);while(!stack.isEmpty() stack.peek() popped[k]){stack.pop();k;} }return stack.isEmpty();}
}
测试结果
