13: Sort A Stack

daisy8867

1. class Solution {
   
2. public:
   
3.     void merge(stack<int>& s, int stride) {
   
4.         int sz = s.size();
   
5.         stack<int> tmp, res;
   
6.         for(int start = 0; start < sz; start += stride) {
   
7.             int end = min(start + stride - 1, sz - 1);
   
8.             int mid = min(start + (stride >> 1) - 1, sz - 1);
   
9.             int t = 0, f = start, i = mid + 1;
   
10.             for(f = start; f <= mid; f++) {
    
11.                 res.push(s.top());
    
12.                 s.pop();
    
13.             }   
    
14.             for(f = start; f <= mid; f++) {
    
15.                 tmp.push(res.top());
    
16.                 res.pop();
    
17.             }   
    
18.             for(i = start, f = mid + 1; i <= mid && f <= end;) {
    
19.                 if(s.top() >= tmp.top()) {
    
20.                     res.push(s.top());
    
21.                     s.pop();
    
22.                     f++;
    
23.                 }   
    
24.                 else {
    
25.                     res.push(tmp.top());
    
26.                     tmp.pop();
    
27.                     i++;
    
28.                 }   
    
29.             }   
    
30.             while(i <= mid) {
    
31.                 res.push(tmp.top());
    
32.                 tmp.pop();
    
33.                 i++;
    
34.             }   
    
35.             while(f <= end) {
    
36.                 res.push(s.top());
    
37.                 s.pop();
    
38.                 f++;
    
39.             }   
    
40.         }   
    
41.         while(!res.empty()) {
    
42.             s.push(res.top());
    
43.             res.pop();
    
44.         }   
    
45.     }   
    
46.     stack<int> sortStack(stack<int>& s) {
    
47.         int sz = s.size();
    
48.         int stride = 2;
    
49.         for(stride = 2; stride < sz; stride <<= 1) {
    
50.             merge(s, stride);
    
51.         }   
    
52.         merge(s, stride);
    
53.         return s;
    
54.     }   
    
55. };

复制代码

daisy8867

uuuouou 发表于 10-6-2015 06:58 AM
可不可以给个代码看看呀

用了两个栈。。不知道题意里的one additional stack是算上输入和输出之外还能另外有一个栈的意思吗