[Algorithm Elementrary] 栈和排序

Thinking Process

We ensure that current stack top is less or equal than the max value from current index to end.So what we need do is to create a list that save the max value from every i index(i = 1, 2, 3, ...) to end. like this:

	for (int i = 1; i <= n; i ++) a[i] = max(b[i], a[i + 1]);

Here a represents the max value from i-index to end and b stands for current value.If current stack top value is greater than a[i + 1] we will ensure that the bigger digit should be poped immediately until the top is less than a[i+1] so that we know ok the bigger digit is not here but furthermore.

Code

#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
stack<int> st;
int a[10000010], b[100000010];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n ; i++ ) cin >> a[i];
    for(int i = n; i >= 1 ; i --) b[i] = max(a[i], b[i + 1]);
    for(int i = 1; i <= n; i++) {
        st.push(a[i]);
        while(!st.empty() && st.top() > b[i + 1]) {
            cout << st.top() << ' ';
            st.pop();
        }
    } 
}