NC115 栈和排序中等通过率35.86%时间限制1秒空间限制256M知识点栈、排序描述给你一个 1 到 n 的排列和一个栈并按照排列顺序入栈你要在不打乱入栈顺序的情况下仅利用入栈和出栈两种操作输出字典序最大的出栈序列排列指 1 到 n 每个数字出现且仅出现一次数据范围 1≤n≤5×104排列中的值都满足 1≤val≤n进阶空间复杂度 O(n) 时间复杂度 O(n)示例1输入[2,1,5,3,4]返回值[5,4,3,1,2]说明操作 栈 结果 2 入栈[2] [] 1 入栈[2\1] [] 5 入栈[2\1\5] [] 5 出栈[2\1] [5] 3 入栈[2\1\3] [5] 4 入栈[2\1\3\4] [5] 4 出栈[2\1\3] [5,4] 3 出栈[2\1] [5,4,3] 1 出栈[2] [5,4,3,1] 2 出栈[] [5,4,3,1,2]示例2输入[1,2,3,4,5]返回值[5,4,3,2,1]思路一注释打印细节版#includestack#includevectorclassSolution{public:/** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * 栈排序 * param a int整型vector 描述入栈顺序 * return int整型vector */vectorintsolve(vectorinta){int*bitnewint[a.size()1]();// 这里的默认值都是0吗vectorintv;stackints;intmaxa.size();// 此时未出栈的最大值已知数是1-n,并且每个数字出现且仅出现一次 // 1-n 有n个数所以a里的所有值个数就是nfor(constautoe:a){cout我要准备插入栈还没有插入eendl;// 如果等于所有数的最大值就连栈也不入直接放到返回的vector里if(maxe){cout发现e是最大值不插入栈直接放入队列endl;v.push_back(e);cout往v里插入eendl;max--;cout最大值更新为maxendl;continue;}// 走到这里就说明此时准备插入的数据不是剩余数的最大值// 但是先得判断此时栈顶元素是不是最大的是最大的就哟先让最大的出栈// 这时还得考虑到出完栈的栈顶是不是还是最大的也要判断// 栈内此时也可能没有元素所以也需要判断一下if(s.size()!0){coute不是最大值要先判断栈顶是不是最大值endl;while(s.size()!0s.top()max)// 直到栈顶不是最大值才结束循环{cout栈顶是最大值s.top()进入队列并出栈endl;v.push_back(s.top());// 如果此时栈顶是最大值就放到vector里cout往v里插入s.top()endl;bit[s.top()]0;// 出栈就置0s.pop();// 然后删除掉栈顶max--;// 要记得最大值--cout最大值更新为maxendl;}// 可以出的最大 值都出完了接下来看看此时的最大值在前面出现过没有出现过就出不了只能优先出比他小一位的如果小一位的还在前面就在匹配更小的cout现在v里有的:;for(autoe:v){coute ;}coutendl;// cout 为什么不进去 因为不是超找a,而死栈里的 endl;while(bit[max])// 这里判断能不能找到前面是否出现过此时的max存在了就只能--{max--;coutmax-- - maxendl;// 在减的过程中可能栈顶的值刚好相等这是就要把栈顶的值出栈出了栈必须置0并且max--,逻辑要清晰一步错就炸了if(s.top()max){cout可以出栈的最大值刚好又是栈顶maxendl;v.push_back(s.top());couts.top()出栈入队列;s.pop();bit[max]0;max--;cout最大值更新为maxendl;}}// 如果减完刚好又是栈顶是max,下次循环会判断到的}// 现在再思考一下有没有可能删除完栈顶最大的元素会不会现在要插入的正好就是最大值理一下逻辑假设此时的最大值插入了进去下一次循环是不是插入的肯定不是最大值但是会先进行栈顶元素是不是最大值的判断就完美实现逻辑所以这里直接插入即可。// 插入coute插入栈正式插入了endl;bit[e]1;// 谁进入了栈就置1到时候出栈也得置0s.push(e);}cout走到这里了endl;while(s.size()){couts.top()入队列并出栈endl;v.push_back(s.top());s.pop();}returnv;}};// 现在的问题 次大值在非常靠前拿不出来现在就得考虑把次次大值拿出来无注释版#includestack#includevectorclassSolution{public:vectorintsolve(vectorinta){int*bitnewint[a.size()1]();vectorintv;stackints;intmaxa.size();for(constautoe:a){if(maxe){v.push_back(e);max--;continue;}if(s.size()!0){while(s.size()!0s.top()max){v.push_back(s.top());bit[s.top()]0;s.pop();max--;}while(bit[max]){max--;if(s.top()max){v.push_back(s.top());s.pop();bit[max]0;max--;}}}bit[e]1;s.push(e);}while(s.size()){v.push_back(s.top());s.pop();}returnv;}};突然想起也能维护个大堆去同步维护栈里已有的元素来代替bit数组。但是效率不如bit数组高。总之也是一种方案吧。思路二注释打印细节版#includestack#includevectorclassSolution{public:vectorintsolve(vectorinta){boolhash[50010]{false};vectorintv;stackints;intmaxa.size();for(autoe:a){// 入栈s.push(e);coute入栈了endl;hash[e]true;// 先更新要出栈的最大值while(hash[max])// 这里就是现在剩余元素的最大值已经出现过了就没必要往后再找了优先让最大值出栈 最大值出栈越早那么他所在的位置越靠前值就越大{cout更新最大值max-;max--;coutmaxendl;}cout出比max大等的值endl;// 出栈while(s.size()s.top()max){couts.top()出栈endl;v.push_back(s.top());s.pop();}}returnv;}};无注释版#includestack#includevectorclassSolution{public:vectorintsolve(vectorinta){boolhash[50010]{false};vectorintv;stackints;intmaxa.size();for(autoe:a){s.push(e);hash[e]true;while(hash[max]){max--;}while(s.size()s.top()max){v.push_back(s.top());s.pop();}}returnv;}};结语思路一可以锻炼代码逻辑控制能力思路一做出来对思路二的理解也容易了许多优先选思路二~思路一编写过程中通过每次错误示例去分析哪里没有思考全面去思考哪里的逻辑有疏漏对题的理解是否到位逐渐完善得到最终代码。