算法tip:栈的可生成性问题

算法tip:栈的可生成性问题

问题描述

给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,判断它们是否可以在最初空栈上进行推入 push 和弹出 pop 操作。(LeetCode 946)

示例:
pushed = [1,2,3,4,5],
popped = [4,5,3,2,1]——>true

pushed = [1,2,3,4,5],
popped = [4,3,5,1,2]——>false

前提

首先,我们知道:

  1. 一个数出栈时,在它之前的数一定已经入栈(或入栈后被弹出)。
  2. 一个数x入栈时,在它之前入栈的y没有在x入栈前弹出,则必须在x出栈后才能弹出。

思路

由这两点我们可得:
(假设pushed是正序的)如果操作可以实现,则在popped中不可能出现这种情况:

设a<b<c,popped中出现...c,a,b...这种序列。(c出栈则说明a,b已经入栈(前提1),a没有在c出栈之前弹出,即a没有在b入栈之前弹出,则a必须在b出栈后弹出(前提2),所以popped中b一定在a之前,因此不可能出现c,a,b)

所以,只需判断popped中不出现c,a,b结构(c,a,b之间可以有其他数)则操作可实现。

但是,由于判断序列过于复杂,所需时间过多,远达不到我们的要求,因此上述思路

只适用于人眼判断,不适用于程序

下面给出程序判断方式。

解题程序

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
         stack<int>temp;
    int j = 0;
    for (auto i = 0; i < pushed.size();) {
        temp.push(pushed[i]);
        ++i;
        while (temp.size()!=0&&temp.top() == popped[j]) {
            temp.pop();
            ++j;
        }//循环判断当栈顶元素与popped想要出栈元素一致时出栈。
    }
    if (temp.size() == 0) {
        return true;
    }
    return false;
    }

解题思路

直接模拟题目的入栈出栈过程,循环入栈,在其间如果top与出栈序列中现在想要出栈的元素相同则出栈。如果操作能执行,则执行到最后栈为空。因为只有一次循环入栈所以时间复杂度为O(N),因为只用了一个栈存放元素,所以空间复杂度为O(N)。

上一篇:Photoshop制作非常高档的金色高光按钮


下一篇:【解决git提交失败】Updates were rejected because the tip of your current branch is behind