题解 | #栈和排序#

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;
    }
};