題目

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.

範例

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

思路

依照題意，pushed跟popped是兩個整數陣列，內容值不會重複出現。

給一個stack，做完上面陣列的操作流程後，stack是空的就回傳true，反之則回傳false。

1. pushed陣列內，持續對stack做push()，直到當前數字是popped內最開頭的值，對stack做pop()。
   
   此時stack=[1, 2, 3, 4] --> stack=[1, 2, 3]，popped已用過4，改以下個數字5最為判斷。
   
2. 繼續完成pushed陣列內處理，重複上一點邏輯。

解題

Java

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;

        for (int num: pushed) {
            stack.push(num);
            while (!stack.isEmpty() && popped[index] == stack.peek()) {
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}

Go

func validateStackSequences(pushed []int, popped []int) bool {
    var index int; 
    stack := make([]int, 0)

    for _, num := range pushed {
        stack = append(stack, num)
        for len(stack) != 0 && stack[len(stack) - 1] == popped[index] {
            stack = stack[:len(stack)-1]
            index++
        }
    }

    return len(stack) == 0
}

Go_實作Stack

func validateStackSequences(pushed []int, popped []int) bool {
    var index int; 
    stack := NewStack()

    for _, num := range pushed {
        stack.Push(num)
        for !stack.IsEmpty() && stack.Peek() == popped[index] {
            stack.Pop()
            index++
        }
    }

    return stack.IsEmpty()
}

type Stack struct {
    list []int
}

func NewStack() *Stack{
    return &Stack{}
}

func (s *Stack) Push(element int) {
    s.list = append(s.list, element)
}

func (s *Stack) Pop() {
    s.list = s.list[: s.Len() -1]
}

func (s *Stack) IsEmpty() bool{
    return s.Len() == 0
}

func (s *Stack) Peek() int {
    return s.list[s.Len()-1]
}

func (s *Stack) Len() int {
    return len(s.list)
}

反思

Java是我工作上主要使用語言，語法使用相對熟悉，內建提供的資料結構跟API比較能在第一時間提供我解題方向。

用go另外寫一版，一方面是在自學後提升一點語法上的熟練度，一方面是想看看不同語言實作同一件事，呈現出來的結果差異。

在Leetcode上執行結果

　　　　執行時間　　記憶體用量
Java 　　4ms　　　　42.5MB
Go　　　9ms　　　　 3.8MB

另外，go內建slice其實已經可以做到不少功能，額外包裝成Stack看起來只是讓原本的程式碼更接近Java的版本。參閱的網路上其他人寫的Stack，在對應的使用場景保留點優化實作上的彈性，多看看不同的寫法，了解其他實作的差異，不失為一個學習的好方式。