一【题目类别】
- 栈
二【题目难度】
- 中等
三【题目编号】
- 946.验证栈序列
四【题目描述】
- 给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。
五【题目示例】
-
示例 1:
- 输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
- 输出:true
- 解释:我们可以按以下顺序执行:
- push(1), push(2), push(3), push(4), pop() -> 4,
- push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
-
示例 2:
- 输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
- 输出:false
- 解释:1 不能在 2 之前弹出。
六【题目提示】
- 1 < = p u s h e d . l e n g t h < = 1000 1 <= pushed.length <= 1000 1<=pushed.length<=1000
- 0 < = p u s h e d [ i ] < = 1000 0 <= pushed[i] <= 1000 0<=pushed[i]<=1000
- p u s h e d 的所有元素互不相同 pushed 的所有元素 互不相同 pushed的所有元素互不相同
- p o p p e d . l e n g t h = = p u s h e d . l e n g t h popped.length == pushed.length popped.length==pushed.length
- p o p p e d 是 p u s h e d 的一个排列 popped 是 pushed 的一个排列 popped是pushed的一个排列
七【解题思路】
- 直接使用栈去模拟整个过程
- 将pushed数组的值入栈,直到与poped数组中的某一个元素相等,此时说明当前栈顶的元素需要出栈,且继续比较poped数组中的下一个元素
- 因为两个输入数组的长度相等,所以遍历结束后,如果栈还有剩余,说明出栈顺序不合理,那么就返回false,否则返回true
八【时间频度】
- 时间复杂度: O ( n ) O(n) O(n), n n n为传入数组的长度
- 空间复杂度: O ( n ) O(n) O(n), n n n为传入数组的长度
九【代码实现】
- Java语言版
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new LinkedList<Integer>();
int index = 0;
for(int i = 0;i<pushed.length;i++){
stack.push(pushed[i]);
while(!stack.isEmpty() && popped[index] == stack.peek()){
stack.pop();
index++;
}
}
return stack.isEmpty();
}
}
- C语言版
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize)
{
int* stack = (int*)malloc(sizeof(int) * 1001);
int top = -1;
int index = 0;
for(int i = 0;i<pushedSize;i++)
{
stack[++top] = pushed[i];
while(top != -1 && popped[index] == stack[top])
{
top--;
index++;
}
}
return top == -1;
}
- Python语言版
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
index = 0
for i in range(0,len(pushed)):
stack.append(pushed[i])
while len(stack) != 0 and popped[index] == stack[-1]:
stack.pop()
index += 1
return len(stack) == 0
- C++语言版
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
int index = 0;
for(int i = 0;i<pushed.size();i++){
st.push(pushed[i]);
while(!st.empty() && popped[index] == st.top()){
st.pop();
index++;
}
}
return st.empty();
}
};
十【提交结果】
-
Java语言版
-
C语言版
-
Python语言版
文章来源:https://www.toymoban.com/news/detail-610560.html -
C++语言版
文章来源地址https://www.toymoban.com/news/detail-610560.html
到了这里,关于【LeetCode每日一题】——946.验证栈序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!