打卡：
直接发现规律 遍历popped数组，如果当前元素比其后一个元素在pushed中的index大，且大于1，直接返回false，否则在pushed数组中删掉相同元素
class Solution {
public:
int index(vector& pushed,int data){
int i = 0;
for(i;i < pushed.size()-1; i++){
if(pushed[i] data)
break;
}
return i;
}
bool validateStackSequences(vector& pushed, vector& popped) {
int data_size = pushed.size();
int id = 0,after = 0,pre = 0;
if(data_size 0|| data_size 1)
return true;
for(int i = 0; i < data_size-1;i++){
id = index(pushed, popped[i]);
after = index(pushed,popped[i+1]);
if ((id-after) > 1)
return false;
else{
pushed.erase(pushed.begin()+id);
}
}
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
i = 0
for ele in pushed:
stack.append(ele)
while stack and stack[-1] == popped[i]:
stack.pop()
i += 1
return not stack
func validateStackSequences(pushed []int, popped []int) bool {
indexM := make(map[int]int, len(pushed))
for i, v := range pushed {
indexM[v] = i + 1
}
var maxI int
s := make([]int, 0, len(pushed))
for _, v := range popped {
i := indexM[v]
if i > maxI {
for k := maxI + 1; k < i; k++ {
s = append(s, k)
}
maxI = i
} else {
if i != s[len(s)-1] {
return false
}
s = s[:len(s)-1]
}
}
return true
}
int n = pushed.length;
Stack<Integer> s = new Stack<>();
int k=0;
for(int i=0;i<n;i++) {
s.push(pushed[i]);
while(!s.isEmpty()&&s.peek()==popped[k]) {
s.pop();
k++;
}
}
return s.isEmpty();
class Solution {
Deque<Integer> deque = new ArrayDeque<>();
public boolean validateStackSequences(int[] pushed, int[] popped) {
int index = 0;
for(int i = 0; i < pushed.length; i ++) {
deque.addFirst(pushed[i]);
while(!deque.isEmpty()
&& index < popped.length
&& deque.peekFirst() == popped[index]) {
deque.pop();
index ++;
}
}
return deque.isEmpty();
}
}
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack, i = [], 0
for num in pushed:
stack.append(num) # num 入栈
while stack and stack[-1] popped[i]: # 循环判断与出栈
stack.pop()
i += 1
return not stack
shuaidi
共以下 42 个回答
打卡：& pushed,int data){
直接发现规律 遍历popped数组，如果当前元素比其后一个元素在pushed中的index大，且大于1，直接返回false，否则在pushed数组中删掉相同元素
class Solution {
public:
int index(vector
int i = 0;
for(i;i < pushed.size()-1; i++){
if(pushed[i] data)
break;
}
return i;
}
bool validateStackSequences(vector& pushed, vector & popped) {
int data_size = pushed.size();
int id = 0,after = 0,pre = 0;
if(data_size 0|| data_size 1)
return true;
for(int i = 0; i < data_size-1;i++){
id = index(pushed, popped[i]);
after = index(pushed,popped[i+1]);
if ((id-after) > 1)
return false;
else{
pushed.erase(pushed.begin()+id);
}
}
return true;
}
};
模拟栈的压入弹出，将栈顶元素与弹出序列比较，如果有相同的就pop栈顶，弹出序列索引+1，一直到没有相同的元素
时间复杂度O(n),空间复杂度O(n)
// 时间复杂度on 空间复杂度on 模拟 stack = new Stack ();
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack
int i = 0;
for(int num : pushed) {
stack.push(num);
while(!stack.isEmpty() && stack.peek() popped[i]) {
stack.pop();
i++;
}
}
return stack.isEmpty();
}
}
时间复杂度O(n)
空间复杂度O(n)
测试通过
class Solution {& pushed, vector & popped) { stk;
public:
bool validateStackSequences(vector
//用一个栈模拟出入栈情况
stack
int n = pushed.size();
for(int i = 0, j = 0; i < n; i++){
stk.emplace(pushed[i]);
while(!stk.empty() && stk.top() popped[j]){
stk.pop();
j++;
}
}
return stk.empty();
}
};
时间复杂度：O（n）
空间复杂度：O（n）
【补卡】Day5：下面是代码
直接模拟即可
做之前一点思路没有看了帅地视频结合GPT基本掌握了
用辅助栈模拟即可。双O(n)
// C++实现& pushed, vector & popped) { s;
class Solution {
public:
bool validateStackSequences(vector
if (pushed.empty()) {
return true;
}
int k = 0;
stack
for (int i = 0; i < pushed.size(); ++i) {
s.push(pushed[i]);
while (!s.empty() && s.top() popped[k]) {
s.pop();
++k;
}
}
return s.empty();
}
};
用一个stack来做辅助，先向栈中压入pushed[i]，然后判断poped[j]stk.top()是否成立，即当前栈顶是否满足弹出条件
时间复杂度：O（n）
空间复杂度：O（n）
”’java
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
}
”’
时间复杂度O(n^2)
空间复杂度O(n)
栈的压入、弹出序列
class Solution { stack =new Stack ();
public boolean validateStackSequences(int[] pushed, int[] popped) {
//可以使用一个辅助栈 遍历pushed推进，顺序对poped对比，如果能比上就出
//当pushed全部进入栈里，但出去顺序不是poped顺序 就false
//其实就是根据poped的顺序出栈
if(pushednull||pushed.length0)
{
return true;
}
Stack
int j=0;
for(int i = 0;i<pushed.length;i++)
{
stack.push(pushed[i]);
while(stack.size()>0&&stack.peek()popped[j])
{
stack.pop();
j++;
}
}
if(stack.size()0)
{
return true;
}else
{
return false;
}
}
}
TS写的
时间复杂度O(n)空间复杂度O(n)时间复杂度：O(n)
空间复杂度：O(n)
栈的压入、弹出
时间复杂度：O(n) 其实n是列表pushed的长度，每个元素最多入栈一次出栈一次，总共2n次
空间复杂度：O(n) 辅助栈有n个元素
“`c++& pushed, vector & popped) { s;
//时间复杂度:O(n)
//空间复杂度:O(n)
class Solution {
public:
bool validateStackSequences(vector
if(pushed.size()<=0) return true; int k=0; stack
int i;
for(i= 0;i < pushed.size();i++) { s.push(pushed[i]); while(! s.empty()&& s.top()= = popped[k]) { s.pop(); k++; } } return s.empty(); } };
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack, i = [], 0
for num in pushed:
stack.append(num) # num 入栈
while stack and stack[-1] popped[i]: # 循环判断与出栈
stack.pop()
i += 1
return not stack
c++ 代码 instack; & pushed, vector & popped)
class Solution {
stack
public:
bool validateStackSequences(vector
{
int count=0;
for(int i=0;i<pushed.size();i++)
{
instack.push(pushed[i]);
while(!instack.empty()&&instack.top()popped[count])
{
instack.pop();
count++;
}
}
return instack.empty();
}
};
代码
时间复杂度：O(N);
空间复杂度：O(N);
时间复杂度：O(N)
空间复杂度: O(N)
不看题解根本想不到
时间复杂度:O(n)
空间复杂度:O(n)
时间复杂度:O(n)
空间复杂度:O(n)
五 stack = new Stack(); popped[k]) {
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
if (pushed null || pushed.length <= 0) {
return true;
}
int k = 0;
Stack
for (int i = 0; i < pushed.length; i++) {
stack.push(pushed[i]);
while (!stack.isEmpty() && stack.peek()
stack.pop();
k++;
}
}
return stack.isEmpty();
}
}
画图更好理解点