946. Validate Stack Sequences - Medium

前往題目

想法

• stack
• 疊代pushed的部分，去匹配popped的元素

思路

1. 循環pushed
2. 每次循環都看stack的頂端是否和popped的元素相符
3. 相符就pop，不相符就繼續
4. 最後看stack是否為空判斷

Code

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack();
        int popPointer = 0;
        for (int push : pushed) {
            stack.push(push); // Push current element

            // Pointer cannot exceed popped's length
            // Stack cannot be empty
            // Match top of the stack and pop element
            while (popPointer < popped.length && !stack.isEmpty() && popped[popPointer] == stack.peek()) {
                stack.pop();
                ++popPointer; // Move pointer
            }
        }
        return stack.isEmpty();
    }
}