Problem
Given two sequences pushed
and popped
with distinct values, return 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:
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:
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed
is a permutation ofpopped
.pushed
andpopped
have distinct values.
Solution: Simulation
Simulate the push/pop operation.
Push element from |pushed sequence| onto stack s one by one and pop when top of the stack s is equal the current element in the |popped sequence|.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua, 8 ms class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> s; auto it = begin(popped); for (int e : pushed) { s.push(e); while (!s.empty() && s.top() == *it) { s.pop(); ++it; } } return it == end(popped); } }; |
Python3
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua, Running time: 40 ms class Solution: def validateStackSequences(self, pushed, popped): s = [] i = 0 for e in pushed: s.append(e) while s and s[-1] == popped[i]: s.pop() i += 1 return i == len(popped) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment