题解 | #栈和排序#

栈和排序

http://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    int searchMax(int* a, int len) {
        int maxNum = a[0];
        for (int i = 1; i < len; i++)
        { 
            if (a[i] > maxNum)
                maxNum = a[i];
        }
        return maxNum;
    }

    vector<int> solve(int* a, int aLen) {
        stack<int> sSort; //用来排序的栈
        vector<int> ret; //用于保存排序后的数组元素 
        int maxNum = 0;
        int i = 0;
        int tmp = 0;

        while (i != aLen)
        {
            maxNum = searchMax(a + i, aLen-i); //找到数组中剩余元素的最大值maxNum
            while (!sSort.empty())
            {
                tmp = sSort.top();
                if (tmp > maxNum) //如果栈顶值大于maxNum,则出栈
                {
                    ret.push_back(tmp);
                    sSort.pop();
                }
                else
                    break;
            }
            for (; a[i] != maxNum; i++) //此时栈顶值小于maxNum,则将该最大值之前的数全部插入栈中
            {
                sSort.push(a[i]);
            }
            ret.push_back(maxNum);
            i++;
        }

        while (!sSort.empty()) //遍历完数组后,如果栈不为空,则将栈中元素全部出栈
        {
            tmp = sSort.top();
            ret.push_back(tmp);
            sSort.pop();
        }

        return ret;
    }
};
全部评论

相关推荐

05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
昨天 11:08
门头沟学院 Java
投递京东等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务