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、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-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 &lt; aLen;i ++){//遍历数组
            s.push(a[i]);//压入栈
            vis[a[i]] = 1;//压入一个数就把对应的数字标记为1
            while(n &amp;&amp; vis[n]) n--;//检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
            while(!s.empty() &amp;&amp; n &lt;= s.top()){
                //然后将栈中&gt;=n的元素出栈
                res.push_back(s.top());
                s.pop();
            }
        }
        //如果栈没为空就按照栈中原样直接出栈
        while(!s.empty()){
            int temp = s.top();
            res.push_back(temp);
            s.pop();
        }
        return res;
    }
}; 

Java版本：

import java.util.*;


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

Python版本:

#
# 栈排序
# @param a int整型一维数组 描述入栈顺序
# @return int整型一维数组
#
class Solution:
    def solve(self , a ):
        # write code here
        s = [] #定义一个栈用来存储数据(我们用数组来模拟)
        n  = len(a)
        res = []#用来返回结果
        vis = [0] *(n+10)#用来标记哪个数字出现过
        for i in a:
            s.append(i)#压入栈
            vis[i] = 1#压入一个数就把对应的数字标记为1
            while n and vis[n]: n-=1#检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
            while s and n <= s[-1]:
                #然后将栈中>=n的元素出栈
                res.append(s[-1])
                s.pop()
        #如果栈没为空就按照栈中原样直接出栈
        while s:
            res.append(s[-1])
            s.pop()
        return res

JavaScript版本：

/**
 * 栈排序
 * @param a int整型一维数组 描述入栈顺序
 * @return int整型一维数组
 */
function solve( a ) {
    // write code here
    let stack = [];//定义一个栈用来存储数据(我们用数组来模拟)
    let res = [];//用于返回结果
    let n = a.length;
    let vis = Array(a.length).fill(0);//用来标记哪个数字出现过
    for(let i = 0;i < a.length;i ++){
        stack.push(a[i]);//压入栈
        vis[a[i]] = 1;//压入一个数就把对应的数字标记为1
        while(n > 0 && vis[n]==1){
            n--;//检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
        }
        while(stack.length && stack[stack.length - 1] >= n){
            //然后将栈中>=n的元素出栈
            res.push(stack[stack.length - 1]);
            stack.pop();
        }
    }
        while (stack.length) {
            //如果栈没为空就按照栈中原样直接出栈
            res.push(stack[stack.length - 1]);
            stack.pop();
        }
        return res;
}
module.exports = {
    solve : solve
};