首页 > 代码库 > 1057. Stack (30)
1057. Stack (30)
/*to solve the problem ,i think we can use stack to maintain the numbers,and list to keep it sorted,which is very important to find the Median number.*/#include<stack>#include<iostream>#include<string>#include<vector>#include<list>#include<algorithm>using namespace std;int main(){ int n; stack<int> stak; string command; int a; cin>>n; while (n--) { cin>>command; if (command == "Push") { cin>>a; stak.push(a); } if (command == "Pop") { if (stak.empty()) { cout<<"Invalid"<<endl; } else { cout<<stak.top()<<endl; stak.pop(); } } if (command == "PeekMedian") { if (stak.empty()) { cout<<"Invalid"<<endl; continue; } vector<int> ls; while (!stak.empty()) { ls.push_back(stak.top()); stak.pop(); } //use the unsorted vector to push_back the stack for (int i = ls.size()-1; i >=0 ; i—) { stak.push(ls[i]); } sort(ls.begin(),ls.end()); cout<<ls[ls.size()%2 == 0 ? ls.size()/2-1:(ls.size()+1)/2-1]<<endl; } }}
At first,i think i could use a temporary stack not only to keep the stack in order but alse to find
the median one . And it is proofed that it is feasible but not effcient ,as everytime we need
to sort the stack as long as we want to use the command “PeekMedian”.
the Time complexity is O(n * log n). then i searched the web. I find someone use the set,
which is virtually a balanced binary tree.so we could reduced the time complexity down to
O(log n). Then i rebuild the code according to this suggestion.
#include <iostream>#include <set>#include <algorithm>#include <stack>#include <cstring>using namespace std;multiset<int> small, big;stack<int> s;int mid;void adjust(){ if (small.size() > big.size() + 1) { auto it = small.end(); --it; big.insert(*it); small.erase(it); } else if (small.size() < big.size()) { auto it = big.begin(); small.insert(*it); big.erase(it); } if (s.size() > 0) { auto it = small.end(); --it; mid = *it; }}int main(){ int n; char op[15]; int top, Key; scanf("%d", &n); while (n--) { scanf("%s", op); if (op[1] == ‘o‘) { if (s.size() == 0) printf("Invalid\n"); else { top = s.top(); s.pop(); printf("%d\n", top); if (mid >= top) { auto it = small.find(top); small.erase(it); } else { auto it = big.find(top); big.erase(it); } adjust(); } } else if (op[1] == ‘u‘) { scanf("%d", &Key); if (s.size() == 0) { small.insert(Key); mid = Key; } else if (Key <= mid) small.insert(Key); else big.insert(Key); s.push(Key); adjust(); } else if (op[1] == ‘e‘) { if (s.size() == 0) printf("Invalid\n"); else printf("%d\n", mid); } }}
1057. Stack (30)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。