GuilinDev

Lc0946

05 August 2008

946 Validate Stack Sequence

题目

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

Given two sequences 

1

pushed
and 
1

popped
with distinct values, return 
1

true
if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:

1
2
3
4
5

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:

1
2
3

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

Constraints:

  • 1

    0 <= pushed.length == popped.length <= 1000

  • 1

    0 <= pushed[i], popped[i] < 1000

  • 1

    pushed
    is a permutation of 
    1

    popped
    .
  • 1

    pushed
    and 
    1

    popped
    have distinct values.

分析

做法是开一个栈直接模拟过程，每次都 push 进一个新元素，然后和 pop 序列不断比对，如果发现一致，则出队。 最后如果 pop 序列都遍历完，则证明合法。这也是贪心的思想。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int len = pushed.length;
        int index1 = 0, index2 = 0;
        
        while (index1 < len && index2 < len) {
            stack.push(pushed[index1]);
            while (!stack.isEmpty() && stack.peek() == popped[index2]) {
                index2++;
                stack.pop();
            }
            index1++;
        }
        return index2 == len; //检查popped数组里面的元素是否pop完
    }
}
This site is open source. Improve this page.