一【題目類別】

• 棧

二【題目難度】

• 中等

三【題目編號】

• 946.驗證棧序列

四【題目描述】

• 給定 pushed 和 popped 兩個序列，每個序列中的 值都不重復，只有當它們可能是在最初空棧上進行的推入 push 和彈出 pop 操作序列的結果時，返回 true；否則，返回 false 。

五【題目示例】

• 示例 1：

  • 輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
  • 輸出：true
  • 解釋：我們可以按以下順序執(zhí)行：
    • 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<=pushed.length<=1000$
• $0<=pushed[i]<=1000$
• $pushed的所有元素互不相同$
• $popped.length==pushed.length$
• $popped是pushed的一個排列$

七【解題思路】

• 直接使用棧去模擬整個過程
• 將pushed數組的值入棧，直到與poped數組中的某一個元素相等，此時說明當前棧頂的元素需要出棧，且繼續(xù)比較poped數組中的下一個元素
• 因為兩個輸入數組的長度相等，所以遍歷結束后，如果棧還有剩余，說明出棧順序不合理，那么就返回false，否則返回true

八【時間頻度】

• 時間復雜度：$O(n)$，$n$為傳入數組的長度
• 空間復雜度：$O(n)$，$n$為傳入數組的長度

九【代碼實現】

1. Java語言版

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int index = 0;
        for(int i = 0;i<pushed.length;i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && popped[index] == stack.peek()){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}

2. C語言版

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize)
{
    int* stack = (int*)malloc(sizeof(int) * 1001);
    int top = -1;
    int index = 0;
    for(int i = 0;i<pushedSize;i++)
    {
        stack[++top] = pushed[i];
        while(top != -1 && popped[index] == stack[top])
        {
            top--;
            index++;
        }
    }
    return top == -1;
}

3. Python語言版

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        index = 0
        for i in range(0,len(pushed)):
            stack.append(pushed[i])
            while len(stack) != 0 and popped[index] == stack[-1]:
                stack.pop()
                index += 1
        return len(stack) == 0

4. C++語言版

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int index = 0;
        for(int i = 0;i<pushed.size();i++){
            st.push(pushed[i]);
            while(!st.empty() && popped[index] == st.top()){
                st.pop();
                index++;
            }
        }
        return st.empty();
    }
};

十【提交結果】

1. Java語言版
   

2. C語言版
   

3. Python語言版
   

4. C++語言版
   文章來源地址http://www.zghlxwxcb.cn/news/detail-610560.html

到了這里，關于【LeetCode每日一題】——946.驗證棧序列的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！