Ex31 栈的压入弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

解题思路

这道题需要一个辅助栈stk。总体的思路如下：

• 当stk的top元素不等于popped元素，不断地将pushed的元素push到stk中。；
• 当stk的top元素等于popped元素，不断地将stk的元素pop出来；
• 重复上述两个步骤，如果pushed和popped同时遍历到了最后，返回true；否则，返回false。

代码

class Solution
{
public:
  bool
  validateStackSequences (std::vector<int> &pushed, std::vector<int> &popped)
  {
    if (pushed.size () != popped.size ())
      return false;
    if (pushed.size () == 0 && popped.size () == 0)
      return true;
    std::stack<int> stk;
    std::vector<int>::iterator pushed_iter = pushed.begin (),
                               popped_iter = popped.begin ();
    while (pushed_iter != pushed.end () && popped_iter != popped.end ())
      {
        if (stk.empty ())
          {
            stk.push (*pushed_iter);
            ++pushed_iter;
          }
        while (stk.top () != *popped_iter)
          {
            stk.push (*pushed_iter);
            ++pushed_iter;
            if (pushed_iter == pushed.end ())
              break;
          }
        while (!stk.empty () && stk.top () == *popped_iter)
          {
            stk.pop ();
            ++popped_iter;
          }
        if (pushed_iter == pushed.end () && popped_iter == popped.end ())
          return true;
      }
    return false;
  }
};

结果

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了83.39%的用户

内存消耗：15.1 MB, 在所有 C++ 提交中击败了23.65%的用户