NC115栈和排序

NC115栈和排序

- 1、题目描述：

- 2、题目链接：

https://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f?tpId=117&tqId=37839&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
-3、 设计思想：

详细操作流程看下图：

-5、代码：
c++版本:

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        stack<int>s;//定义一个栈用来存储数据
        int n = aLen;
        vector<int>res;//用来返回结果
        vector<bool> vis(aLen + 10,0);//用来标记哪个数字出现过
        for(int i = 0;i < aLen;i ++){//遍历数组
            s.push(a[i]);//压入栈
            vis[a[i]] = 1;//压入一个数就把对应的数字标记为1
            while(n && vis[n]) n--;//检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
            while(!s.empty() && n <= s.top()){
                //然后将栈中>=n的元素出栈
                res.push_back(s.top());
                s.pop();
            }
        }
        //如果栈没为空就按照栈中原样直接出栈
        while(!s.empty()){
            int temp = s.top();
            res.push_back(temp);
            s.pop(