【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