Leetcode第946题

题目描述

https://leetcode.cn/problems/validate-stack-sequences/

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

个人思路

不会使用Java的栈数据，然后模拟了一下出入栈的过程，栈序列第一个元素只能与栈顶元素或未放入元素相同时，才能输出。输出之后，栈顶下滑，继续刚才的操作，直到popped了length个元素。

class Solution{
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int count=0;
        for (int i=0;i<pushed.length;i++){
            if (find(pushed,i,popped,0,count))return true;
        }
        return false;
    }

    public boolean find(int[] pushed,int i,int[] popped,int j,int count){
        if (count==pushed.length)return true;
        while (pushed[i]==-1 && i>0)i--;
        for(;i<pushed.length;i++){
            if (pushed[i]==popped[j]){
                pushed[i]=-1;
                count++;
                if(find(pushed,Math.abs(i-1),popped,j+1,count))return true;
            }
        }
        return false;
    }
}

代码优化

无

参考思路

直接辅助的堆栈结构，用现成的方法实现出入栈，如果最后栈里还有元素，说明按照指定序列不能出栈，避免递归。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0; 
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

收获

JAVA的数据结构Stack的用法