栈，列表（指针模拟栈），2 解法求解《946. 验证栈序列》
例题
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 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列
思路
- 找到
pushed中最先被弹出的是popped[0] - 每次从
pushed弹出后，有两种选择- 继续
pop()弹出 - 推入
pushed中下一个
- 继续
答案
栈
var validateStackSequences = function(pushed, popped) {
const n = pushed.length, stack = []
for (let i = j = 0; i < n; i++) {
stack.push(pushed[i])
while (stack.length && stack[stack.length - 1] === popped[j]) {
stack.pop()
j++
}
}
return stack.length === 0
};function validateStackSequences(pushed: number[], popped: number[]): boolean {
const n = pushed.length, stack = []
for (let i = 0, j = 0; i < n; i++) {
stack.push(pushed[i])
while (stack.length && stack[stack.length - 1] === popped[j]) {
stack.pop()
j++
}
}
return stack.length === 0
};class Solution {
function validateStackSequences($pushed, $popped) {
$stack = [];
$j = 0;
foreach ($pushed as $v) {
$stack []= $v;
while (count($stack) && end($stack) === $popped[$j]) {
array_pop($stack);
$j++;
}
}
return count($stack) === 0;
}
}func validateStackSequences(pushed []int, popped []int) bool {
stack, j := []int{}, 0
for _, v := range pushed {
stack = append(stack, v)
for len(stack) > 0 && stack[len(stack) - 1] == popped[j] {
stack = stack[:len(stack) - 1]
j++
}
}
return len(stack) == 0
}class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new ArrayDeque<Integer>();
int j = 0, n = pushed.length;
for (int v : pushed) {
stack.push(v);
while (stack.isEmpty() == false && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}public class Solution {
public bool ValidateStackSequences(int[] pushed, int[] popped) {
Stack<int> stack = new Stack<int>();
int j = 0;
foreach (int v in pushed) {
stack.Push(v);
while (stack.Count > 0 && stack.Peek() == popped[j]) {
stack.Pop();
j++;
}
}
return stack.Count == 0;
}
}class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
int j = 0;
for (int v : pushed) {
st.emplace(v);
while (st.empty() == false && st.top() == popped[j]) {
st.pop();
j++;
}
}
return st.empty();
}
};class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
st, j = list(), 0
for _, v in enumerate(pushed):
st.append(v)
while len(st) and st[-1] == popped[j]:
st.pop()
j += 1
return len(st) == 0列表 · 指针模拟栈
var validateStackSequences = function(pushed, popped) {
const n = pushed.length, stack = []
let m = 0
for (let i = j = 0; i < n; i++) {
stack[m++] = pushed[i]
while (m > 0 && stack[m - 1] === popped[j]) {
m--
j++
}
}
return m === 0
};
function validateStackSequences(pushed: number[], popped: number[]): boolean {
const n = pushed.length, stack = new Uint16Array(n)
let m = 0
for (let i = 0, j = 0; i < n; i++) {
stack[m++] = pushed[i]
while (m > 0 && stack[m - 1] === popped[j]) {
m--
j++
}
}
return m === 0
};```
```php []
class Solution {
function validateStackSequences($pushed, $popped) {
$stack = array_fill(0, count($pushed), 0);
$m = 0;
$j = 0;
foreach ($pushed as $v) {
$stack[$m++] = $v;
while ($m > 0 && $stack[$m - 1] === $popped[$j]) {
$m--;
$j++;
}
}
return $m === 0;
}
}func validateStackSequences(pushed []int, popped []int) bool {
stack, j, m := make([]int, len(pushed)), 0, 0
for _, v := range pushed {
stack[m], m = v, m + 1
for m > 0 && stack[m - 1] == popped[j] {
m, j = m - 1, j + 1
}
}
return m == 0
}class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int[] stack = new int[pushed.length];
int m = 0, j = 0;
for (int v : pushed) {
stack[m++] = v;
while (m > 0 && stack[m - 1] == popped[j]) {
m--;
j++;
}
}
return m == 0;
}
}public class Solution {
public bool ValidateStackSequences(int[] pushed, int[] popped) {
int[] stack = new int[pushed.Length];
int m = 0, j = 0;
foreach (int v in pushed) {
stack[m++] = v;
while (m > 0 && stack[m - 1] == popped[j]) {
m--;
j++;
}
}
return m == 0;
}
}bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
int* stack = malloc(sizeof(int) * pushedSize);
int m = 0;
for (int i = 0, j = 0; i < pushedSize; i++) {
stack[m++] = pushed[i];
while (m > 0 && stack[m - 1] == popped[j]) {
m--;
j++;
}
}
free(stack);
return m == 0;
}class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
vector<int> st(pushed.size());
int m = 0, j = 0;
for (int v : pushed) {
st[m++] = v;
while (m > 0 && st[m - 1] == popped[j]) {
m--;
j++;
}
}
return m == 0;
}
};class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
st, m, j = [0] * len(pushed), 0, 0
for _, v in enumerate(pushed):
st[m], m = v, m + 1
while m > 0 and st[m - 1] == popped[j]: m, j = m - 1, j + 1
return m == 0