劍指offer 面試題21.22―棧操作以及判斷彈出序列
來源：程序員人生 發布時間：2015-06-18 08:51:15 閱讀次數：3887次
題目：
1.定義棧數據結構，請在該類型中實現1個能夠得到棧的最小元素的min函數。在該棧中，調用min、push和pop的時間復雜度都是O(1)。
2.輸入兩個整數序列，第1個序列表示棧的壓入順序，請判斷第2個序列是不是為該棧的彈出順序。假定壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，
序列 4,5,3,2,1是該壓棧序列對應的1個彈出序列，但4,3,5,1,2就不多是該壓棧序列的彈出序列。
題目1解答：
//m_data數據棧，m_min輔助棧
push(int value)
{
m_data.push(value);
if(m_min.size()==0 || value<m_min.top())
m_min.push(value);
else
m_min.push(m_min.top());
}
pop()
{
m_data.pop();
m_min.top();
}
min()
{
return m_min.top();
}
題目2解答：
我們可以建立1個輔助棧來存儲入棧的部份序列，可以o(n)的時間復雜度內解決問題。出棧序列的元素首先與輔助棧（若不空）的棧頂元素比較，若不等再與入棧序列的元素比較。若與入棧序列的元素仍不相等，則當前入棧序列的元素進入輔助棧，出棧序列確當前元素與入棧序列的后面元素繼續比較。若輔助棧的棧頂元素和入棧序列的全部元素都不與出棧序列確當前元素相等，則該序列不是1個正確的出棧序列；若所有出棧序列元素都比較完，則是1個正確的出棧序列。
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
int a[100010],b[100010];
stack<int> s;
int main()
{
int n,i,j;
while(cin>>n)
{
for( i=0; i<n; i++ )
cin>>a[i];
for( i=0; i<n; i++ )
cin>>b[i];
i=j=0;
while( !s.empty() ) //這個很關鍵，由于有多個測試用例，所以需要清空上個測試用例的棧。
s.pop();
while(i<=n)
{
if( !s.empty() && b[j]==s.top() )
{
s.pop();
j++;
}
else
{
if( i==n )
break;
s.push(a[i]);
i++;
}
}
if( j == n )
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
