|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
用一个辅助栈存放单调的序列,栈顶->栈底递减,当发现原栈栈顶>辅助栈栈顶时,先取出这个数,再将辅助栈中的数依次压入原栈,直到辅助栈的栈顶元素不小于这个数,实际是类似插入排序的思想,复杂度也是O(N^2)的
- class Solution {
- public:
- stack<int> sortStack(stack<int> &s) {
- if(s.size() < 2) return s;
-
- stack<int> t;
- while(true){
- do{
- t.push(s.top()); s.pop();
- }while(!s.empty() && s.top() <= t.top());
- if(s.empty()) break;
-
- int tmp = s.top(); s.pop();
- while(!t.empty() && t.top() < tmp){
- s.push(t.top()); t.pop();
- }
- t.push(tmp);
- }
- while(!t.empty()){
- s.push(t.top()); t.pop();
- }
- return s;
- }
- };
复制代码
|
|