2020-05-15

1.題目描述

驗證棧序列

2.題解

這個題目我本科的一位老師在給我們上算法課的時候講過，他說關鍵是要明白我們什么時候需要入棧，什么 時候需要出棧，題目是要返回pushed數組能不能經過一系列入棧、出棧操作得到popped數組，對于pushed 數組中的元素而言，什么時候要入棧呢？如果說popped數組中的元素還沒有在pushed數組中找到的話，就需 要入棧一直到找到該元素為止，如果找不到，直接返回false，如果棧頂元素等于當前pusheed數組的元素值， 則進行出棧操作即可，最后再看能不能通過一系列出棧操作得到popped數組剩下的元素。

3.代碼

class Solution { public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {int l=pushed.size();int i=0,j=0; // i->pushed，j->poppedstack<int> mystack;while (j<l&&i<l){if (!mystack.empty()&&mystack.top()==popped[j]){ // 出棧mystack.pop();j++;continue;}while (i<l&&pushed[i]!=popped[j]){ // 入棧mystack.push(pushed[i]);i++;}if (i>=l) return false;i++;j++;}while (j<l){if (popped[j]!=mystack.top()) return false;j++;mystack.pop();}return true;} };

總結

以上是生活随笔為你收集整理的946. 验证栈序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。