劍指Offer系列(java版,詳細解析)31.棧的壓入、彈出序列

程序員社區 2022-01-08 03:23:22 阅读数:297

offer 系列 java 解析 序列

題目描述

劍指 Offer 31. 棧的壓入、彈出序列

難度中等152

輸入兩個整數序列,第一個序列錶示棧的壓入順序,請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如,序列 {1,2,3,4,5} 是某棧的壓棧序列,序列 {4,5,3,2,1} 是該壓棧序列對應的一個彈出序列,但 {4,3,5,1,2} 就不可能是該壓棧序列的彈出序列。

示例 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. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushedpopped 的排列。

測試用例

  • 功能測試(輸入的兩個數組含有多個數字或者只有一個數字;第二個數組是或者不是第一個數組錶示的壓入序列對應的棧的彈出序列)
  • 特殊輸入測試(輸入兩個空指針)

題目考點

  • 考察應聘者對棧的理解
  • 考察應聘者用舉例分析複雜問題的能力

解題思路

  1. 建立一個輔助棧
  2. 當棧為空或者棧的棧頂元素不為彈出序列需要的彈出元素時,將壓入序列繼續壓入棧直到棧頂為彈出元素
  3. 當棧頂元素為彈出元素時,則彈出該元素
  4. 當壓入序列的所有元素都壓入棧時,依然找不到匹配的彈出元素,則不是彈出序列

解題

class Solution {
 public boolean validateStackSequences(int[] pushed, int[] popped) {
 Stack<Integer> stack = new Stack<>(); int j = 0; for(int i = 0;i<pushed.length;i++){
 stack.push(pushed[i]); while(!stack.isEmpty() &&stack.peek() == popped[j] ){
 j++; stack.pop(); } } return stack.isEmpty(); }}
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080323217199.html