数学森林/洛谷P1750 出栈序列

原创新思路求解出栈序列问题。

问题描述：

数学家小王经过千辛万苦长途跋涉终于来到了数学森林。无奈森林入口有很多个小矮人镇守。小矮人拿出一套题目让小王抽取一道题目说解出题目方能进入数学森林。题目如下：给定一个大小为c（最多可以同时存储c个元素）的堆栈，输入n个入栈的数，请输出所有出栈序列里第一个元素最小的序列（若第一个元素最小的序列有多个，则令第二个尽可能小；若仍有多个，则令第三个最小，以此类推）。
聪敏的你能不能写一段代码，帮助数学家小王解出这个难题。

本题考察栈的使用。

算法思想：

附在代码注释当中。

代码如下：

#include <iostream>
#include<algorithm>
#include<cmath>
#include<stack> 
#include<queue>

using namespace std;


bool check(int start, int c, stack<int>& test, vector<int>& a) {
    int end = min(start + c - (int)test.size(), (int)a.size());
    for (int i = start; i < end; i++) { // 确保不会超出数组边界
        if (a[i] < test.top()) {
            return true;
        }
    }
    return false;
}

int main(){
	int c,n,x;
	stack<int> test;
	cin>>n>>c;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>x;
		a[i]=x;
	}
	int first=0;
	for(int i=0;i<n;i++){
		if(test.size()<c){
			test.push(a[i]);//如果栈有位置，则直接入栈 
		}
		else{
			//栈满，说明栈顶元素是栈中最小元素，直接出栈并输出 
			cout<<test.top()<<" ";
			test.pop();
			i--;
			continue;//此时栈已有一个空位置，重新进入循环，继续 
		
		}
		if(i!=n-1){
			if(!test.empty() && test.top()>a[i+1]){
				continue;
			}
			while(!test.empty() && test.top()<a[i+1]){
				if(!check(i+1,c,test,a)){  //检查后方可以入栈元素中是否有比当前栈顶元素更小的 
					cout<<test.top()<<" ";  //如果没有，说明栈顶元素为最小，出栈并输出 
					test.pop();
				}
				else{//如果后方有更小的元素可以入栈，继续判断 
					break;
				}
			}
		}
		else{//当前元素为最后一个入栈的元素 
			while(!test.empty()){
				cout<<test.top()<<" ";
			    test.pop();
			}
		}
		
	}
	
    return 0;
}