題目：輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序蜡歹，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序贴谎。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序季稳，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列擅这，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長度是相等的）
練習(xí)地址
https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
參考答案
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int i = 0;
for(int num : pushed) {
stack.push(num); // num 入棧
while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循環(huán)判斷與出棧
stack.pop();
i++;
}
}
return stack.isEmpty();
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)景鼠。
- 空間復(fù)雜度：O(n)仲翎。
