8

给定两个唯一的数字序列：push order of stack和pop order of stack中的数字push order按升序排列，现在问pop order合法与否？

例如，push order是 1 2 3 4 5，所以 4 5 3 2 1 是合法的弹出命令，因为我们可以像这样 push 和 pop：

push 1, push 2, push 3, push 4, pop, push 5, pop, pop, pop, pop

所以弹出命令： 4 5 3 2 1 是合法的，而 4 3 5 1 2 不是合法的弹出命令。

4

4 回答 4

4

Since your push sequence is in ascending order, then when you see a number N in your pop queue, then all numbers that is 1) below N and 2) not yet popped, must be popped in descending order.

For example, 4 3 5 1 2 is not a valid order, since when we see '4' popped, than all numbers smaller than '4' but not yet popped before must be popped in descending order. However, popping '1' first and then '2' violates this property.

于 2013-07-24T00:06:49.297 回答
3

一种选择是实际构建堆栈：

X对于弹出顺序中的每个数字：

  • 如果此数字与栈顶不同（或栈为空），则从 push 顺序中 push 数字，直到 push 为止X。如果你推了所有的号码都没有找到X，就没有办法得到pop order。
  • 流行音乐X

请注意，这实际上并不要求推送顺序是升序的。

X如果小于堆栈顶部，则可以通过失败来利用排序来稍微优化上述内容（提前失败） 。

由于您最多只推送每个元素一次，因此以上是线性时间（您不能做得更好）和线性空间。

例子：

Push: 1 2 3 4 5  
Pop: 4 5 3 2 1

Processing: 4
    Stack empty -> push until 4 is on the top of the stack.
    Stack: 1 2 3 4
    Pop 4
    Stack: 1 2 3

Processing: 5
    3 != 5 -> push until 5 is on the top of the stack.
    Stack: 1 2 3 5
    Pop 5
    Stack: 1 2 3

Processing: 3
    Pop 3
    Stack: 1 2

Processing: 2
    Pop 2
    Stack: 1

Processing: 1
    Pop 1
    Stack: 

Done.
于 2013-07-24T08:03:14.230 回答
2

假设：推送订单和弹出订单包含完全相同的数字。如果这不是一个有效的假设，则可以在线性时间内使用散列集（或带有计数的散列映射，如果可能存在重复）对其进行验证，尽管这会损害 O(1) 空间复杂度。

思路：弹出顺序中的每个元素必须要么小于它之前的元素，要么大于迄今为止的最大值，否则弹出顺序无效。

这可以通过跟踪最大值在 O(n) 时间和 O(1) 空间中进行检查。

为什么这样有效：

推送顺序是升序，因此，无论何时弹出元素：

  1. 堆栈也将始终按升序排列，并且
  2. 推送顺序中的下一项将始终大于堆栈中看到的最大元素。

所以有两种选择：

  • 连续两次弹出操作 - 在这种情况下，第二个元素会更小
  • 两个弹出操作之间有一个或多个推送操作 - 在这种情况下，第二个元素将大于最大值（从 2 开始。）

例子：

4 5 3 2 1有效，因为 5 > max (4)、3 < 5、2 < 3 和 1 < 2。

4 3 5 1 2无效，因为 2 > 1 但 2 < max (5)。

1 2 3 5 4有效，因为 2 > max (1)、3 > max (2)、5 > max (3) 和 4 < 5。

于 2013-07-24T09:54:41.110 回答
1

解决方案：

i: from 1 to n
j: from 1 to n, used to traverse the sequence seq[1...n]
stack: empty at the beginning
while i <= n || j <= n
    IF stack is empty,
        push i into stack, i plus 1;
    ELSE IF the top of stack is equal to seq[j]
        pop from stack, j plus 1;
    ELSE IF the top of stack is larger than seq[j]
        illegal sequence! Stop here!
    ELSE 
        push i into stack, i plus 1;
legal sequence if the stack is empty!

示例 1：{1, 2, 4, 3}，合法序列

In the beginning, i = 1, j = 1, and stack is empty.

1. stack is empty: 
   stack = {1}, i = 2, j = 1.

2. top of stack 1 is equal to seq[j] = 1: 
   stack = {}, i = 2, j = 2.

3. stack is empty: 
   stack = {2}, i = 3, j = 2.

4. top of stack 2 is equal to seq[j] = 2: 
   stack = {}, i = 3, j = 3.

5. stack is empty: 
   stack = {3}, i = 4, j = 3.

6. top of stack 3 is smaller than seq[j] = 4: 
   stack = {3, 4}, i = 5, j = 3.

7. top of stack 4 is equal to seq[j] = 4: 
   stack = {3}, i = 5, j = 4.

8. top of stack 3 is equal to seq[j] = 3:
   stack = {}, i = 5, j = 5.

示例 2：{1, 4, 2, 3}，非法序列

In the beginning, i = 1, j = 1, and stack is empty.

1. stack is empty: 
   stack = {1}, i = 2, j = 1.

2. top of stack 1 is equal to seq[j] = 1: 
   stack = {}, i = 2, j = 2.

3. stack is empty: 
   stack = {2}, i = 3, j = 2.

4. top of stack 2 is smaller than seq[j] = 4: 
   stack = {2, 3}, i = 4, j = 2.

5. top of stack 3 is smaller than seq[j] = 4: 
   stack = {2, 3, 4}, i = 5, j = 2.

6. top of stack 4 is equal to seq[j] = 4: 
   stack = {2, 3}, i = 5, j = 3.

7. top of stack 3 is larger than seq[j] = 2: 
   illegal sequence, stop here.

我正在尽力解释我的想法，希望我已经把事情说清楚了。

于 2013-07-24T00:21:26.893 回答