【LeetCode】946. Validate Stack Sequences

題目

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

思路

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)
}

反思

在Leetcode上執行結果

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