題目
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。
- pushed陣列內，持續對stack做push()，直到當前數字是popped內最開頭的值，對stack做pop()。
此時stack=[1, 2, 3, 4] --> stack=[1, 2, 3]，popped已用過4，改以下個數字5最為判斷。 - 繼續完成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，在對應的使用場景保留點優化實作上的彈性，多看看不同的寫法，了解其他實作的差異，不失為一個學習的好方式。
