题解 | 栈和排序（C++版本）

（施工中...）

描述：
给你一个1到n的排列和一个栈，入栈顺序给定。你要在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，对数组进行从大到小排序，输出排序结果。当无法完全排序时，请输出字典序最大的出栈序列。

方法一：暴力破解法
我们可以找到一个规律：
步骤一：找出整个数组中的最大值；
步骤二：将该最大值之前的数全部插入栈中；
步骤三：在未插入栈中的数组中找到最大值；
步骤四：将该最大值与栈顶值比较，如果栈顶值大于该最大值，则出栈，直到栈顶值小于该最大值，然后回到步骤二，直到全部元素入栈；
步骤五：栈中全部元素出栈。

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