P129 验证入栈出栈序列

描述#

这个题目说的是，给你两个不包含重复元素的数组，你要判断它们是否可以组成一对合法的入栈出栈序列。

比如说，给你的入栈序列是：
1, 2, 3, 4, 5
给你的出栈序列是：
4, 5, 3, 2, 1
根据入栈序列，我们可以先把 1,2,3,4 入栈，然后把 4 出栈，我们就得到出栈序列中的第 0 个元素 4：
4, 5, 3, 2, 1
接着入栈 5，然后把 5 出栈，我们就得到出栈序列中的第 1 个元素 5：
4, 5, 3, 2, 1
接下来再依次出栈 3,2,1，也就得到出栈序列中最后 3 个数字：
4, 5, 3, 2, 1
因此，这两个数组是一对合法的入栈出栈序列。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed == null || popped == null || pushed.length != popped.length)
      return false;

    Stack<Integer> stack = new Stack<>();
    int p = 0;
    for (int num: pushed) {
      stack.push(num);
      while (!stack.isEmpty() && stack.peek() == popped[p]) {
        stack.pop();
        ++p;
      }
    }
    return stack.isEmpty();
  }

  // Time: O(n), Space: O(n)
  public boolean validateStackSequencesArray(int[] pushed, int[] popped) {
    if (pushed == null || popped == null || pushed.length != popped.length)
      return false;

    int[] stack = new int[pushed.length];
    int p = 0, top = -1;
    for (int num: pushed) {
      stack[++top] = num;
      while (top != -1 && stack[top] == popped[p]) {
        --top;
        ++p;
      }
    }
    return top == -1;
  }

}