【算法作业】单调栈排序

问题描述

1. 给栈结构设计一个求最小值的操作，要求入栈、出栈以及求最小值均在O(1)完成。

2. 给出策略利用栈去完成一个序列的排序，并分析相应的性能。

解题思路

第一题

1. 维护两个栈，一个是普通栈 normalStack，一个是小顶栈 minStack。

2. 入栈操作就是normalStack正常push，minStack当栈为空或栈顶元素比要入栈小时push进去。
   这样就可保证minStack的top为最小值，且入栈操作时间复杂度为O(1)。

3. 出栈操作normalStack同理正常pop，minStack当top元素的值等于normalStack的top元素时就出栈。
   这样就可以保证每次pop弹出元素后minStack的top仍为最小值。时间复杂度为O(1)。

4. 求最小值只需要返回minStack的top即可。时间复杂度为O(1)。

第二题

使用栈进行排序的一个常见策略是利用一个额外的临时栈，将原始栈中的元素依次弹出并按顺序插入到辅助栈中。具体步骤如下：

1. 维护两个栈，一个是主栈mainStack，一个是临时栈tempStack。

2. 入栈时，如果mainStack主栈为空或者要入栈的元素x小于栈顶，就直接push到mainStack。
   否则，将mainStack上方小于x的所有元素依次弹出，再push到tempStack中去，然后将x压入mainStack中，
   再将tempStack中的所有元素依次pop再push到mainStack中。最后得到从栈顶到栈底从小到大的排序。

3. 入栈操作需要将mainStack的元素倒出来，再到回去，时间复杂度为O(2n)，去掉常量为O(n)，
   一共有n个元素，所以总的时间复杂度为O($n^2$)。

完整代码

T1

C++源代码

#include <stack>
#include <iostream>

using namespace std;

class MinStack {
private:
    stack<int> normalStack;
    stack<int> minStack;

public:

    void push(int x) {
        normalStack.push(x);
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }

    void pop() {
        if (normalStack.top() == minStack.top()) {
            minStack.pop();
        }
        normalStack.pop();
    }

    int top() {
        return normalStack.top();
    }

    int getMin() {
        return minStack.top();
    }
};

int main() {
    MinStack minStack;
    int n;
    cout<<"请输入元素个数:";
    cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		minStack.push(x);
		cout<<"当前最小值："<<minStack.getMin()<<endl;
	}
		 
    return 0;
}

运行结果

请输入元素个数:5
8
当前最小值：8
2
当前最小值：2
4
当前最小值：2
5
当前最小值：2
1
当前最小值：1

T2

C++源代码

#include <stack>
#include <iostream>

using namespace std;

stack<int> mainStack;

class SortStack {
private:
    stack<int> tempStack;
public:
    void push(int x) {
        if(mainStack.empty() || x <= mainStack.top()){
        	mainStack.push(x);
		}
		else{
			while(!mainStack.empty() && mainStack.top() <= x){
				tempStack.push(mainStack.top());
				mainStack.pop();
			}
			mainStack.push(x);
			while(!tempStack.empty()){
				mainStack.push(tempStack.top());
				tempStack.pop();
			} 
		}
    }

};

int main() {
    int n;
    SortStack sortStack;
    cout<<"请输入元素个数：";
    cin>>n;
    cout<<"请输入"<<n<<"个元素:"<<endl;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		sortStack.push(x); 
	}
		
	for(int i=1;i<=n;i++){
		cout<<mainStack.top()<<" ";	 
		mainStack.pop();
	}
			 
    return 0;
}

运行结果

请输入元素个数：5
请输入5个元素:
2 1 3 5 4
1 2 3 4 5