CodingQuestion/src/LeetCode-946-Validate-Stack-Sequences.java at master · drinkbeer/CodingQuestion · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    // 1. Validate using a real stack
//     public boolean validateStackSequences(int[] pushed, int[] popped) {
//         Stack<Integer> stack = new Stack<>();
//         for (int i = 0, j = 0; j < popped.length;) {
//             // System.out.println(stack.toString() + "  " + i + "   " + j);
//             if (i >= pushed.length) {

//                 if (stack.peek() != popped[j]) return false;
//                 j++;
//                 stack.pop();
//                 continue;
//             }

//             stack.push(pushed[i]);
//             i++;

//             while (!stack.isEmpty() && stack.peek() == popped[j]) {
//                 stack.pop();
//                 j++;
//             }
//         }

//         return stack.isEmpty();
//     }

    // 2. A more concise solution
    /*
    https://leetcode.com/problems/validate-stack-sequences/discuss/197667/Java-straight-forward-stack-solution.
    */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stk = new Stack<>();
        int i = 0;
        for (int p : pushed) {
            stk.push(p);
            while (!stk.isEmpty() && stk.peek() == popped[i]) {
                stk.pop();
                ++i;
            }
        }
        return stk.empty();
    }
}