[LeetCode/力扣][Java] 0946. 验证栈序列（Validate Stack Sequences）

题目描述：

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

示例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 之前弹出。

题目详情：0946#验证栈序列

思路：第一个想法是用数组flagarr模拟栈来记录当前push的数据，然后poped中的元素依次与flagarr进行比较，若两个元素不等，则push,相等则pop。后来想了想试试用一个真正的栈（stack）来模拟是不是更方便，于是第一个用栈解决的版本出现了。

代码1（Stack）：

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        //用栈记录当前入栈序列
        Stack<Integer> stk = new Stack<Integer>();
        int j = 0;
        int len = pushed.length;
        for (int i = 0; i < len; i++) {
            while (stk.empty() || (int)stk.peek() != popped[i]) {
                if (j < len) {
                    stk.push(pushed[j]);
                    j++;

                } else return false;
            }
            if (stk.peek() == popped[i]) stk.pop();
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

用辅助栈虽然实现起来很简单：pushed数组只负责入栈，poped数组只负责跟栈顶比较。但是耗时很大（4ms，只击败了12.8%）。看了眼评论区同样有用数组的，于是又写了一个版本：
代码2（Array）:

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        //用标记数组进行判断
        int[] flagarr = new int[1009];
        int len = pushed.length;
        int idx = 0;
        int size = 0;
        int j = 0;
        for (int i = 0; i< len; i++) {
            flagarr[idx] = pushed[i];
            idx++;
            while (idx > 0 && popped[j] == flagarr[idx-1]) {
                idx--;
                j++;
            }    
        }
        if (idx > 0) return false;
        else return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Array版的耗时1ms，击败92.8%。好多了。
评论区高赞还有一种就地利用pushed数组辅助的方法但我还没细看，估计原理大差不差，这道题还是挺简单的。

tips:打算从C++转Java了，一来毕竟不是打比赛，刷题主要是为了练习算法思路，不用太过计较耗时。二来，C++有时候指针还挺麻烦的，额外去查语言的API也很耗费精力，而且自己也是投的JAVA开发岗，用Java也比较省心。（我永远喜欢C++(刷题)）