HackMD
946.Validate Stack Sequences
tags: Medium,Array,Stack
題目描述
Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.
範例
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.
Constraints:
- 1 <=
pushed.length<= 1000 - 0 <=
pushed[i]<= 1000 - All the elements of
pushedare unique. popped.length==pushed.lengthpoppedis a permutation ofpushed.
解答
Python
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
push_idx, pop_idx, stack = 0, 0, []
while push_idx < len(pushed) or stack:
if stack and stack[-1] == popped[pop_idx]:
stack.pop()
pop_idx += 1
else:
if push_idx < len(pushed):
stack.append(pushed[push_idx])
push_idx += 1
else:
return False
return not stack
Ron ChenThr, Apr 13, 2023
Javascript
function validateStackSequences(pushed, popped) {
const stack = [];
for (let i = 0; i < pushed.length; i++) {
stack.push(pushed[i]);
while (stack.length && stack[stack.length - 1] === popped[0]) {
stack.pop();
popped.shift();
}
}
return stack.length === 0;
}
MarsgoatThr, Apr 13, 2023
TypeScript
function validateStackSequences(pushed: number[], popped: number[]): boolean {
const stack: number[] = [];
function checkTopAndPop(stack: number[]) {
if (stack[stack.length - 1] === popped[0]) {
stack.pop();
popped.shift();
if (stack.length !== 0) {
checkTopAndPop(stack);
}
}
}
pushed.forEach((num) => {
stack.push(num);
checkTopAndPop(stack);
});
return stack.length === 0;
}
SheepThr, Apr 13, 2023
