Validate Stack Sequences
LeetCode https://leetcode.cn/problems/validate-stack-sequences/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new ArrayDeque<Integer>();
int n = pushed.length;
for (int i = 0, j = 0; i < n; i++) {
stack.push(pushed[i]);
while (!stack.isEmpty() && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}
Complexity
- Time = O(n)
- Space = O(n)
This post is licensed under CC BY 4.0 by the author.