Leetcode 946 Validate Stack Sequences

发表于 |

给定两个序列，pushed和popped（里面每个值都不同），如果这两个序列能真实对应着某种入栈出栈顺序则返回true，否则返回false.

Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Note:

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushed is a permutation of popped.
  4. pushed and popped have distinct values.

思路分析：
既然题目问这能不能模拟真实栈的操作，那么我们就用栈来模拟一下，如果最后栈为空，那说明这确实是真实的操作。

我们用两个指针i,j分别对应push和pop序列
如果push[i] != pop[j]，那么stack.append(push[i])
如果pop[j] == stack[-1]，那么stack.pop()
最后判断stack是否为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def validateStackSequences(self, p1, p2):
        stack = []
        i,j = 0,0
        n = len(p1)
        while i < n and j < n:
            while i < n and p1[i] != p2[j]:
                stack.append(p1[i])
                i += 1
            j += 1; i += 1
            while j < n and stack and p2[j] == stack[-1]:
                stack.pop()
                j += 1
        return not stack