题解44 |N数排序出栈前，一组一栈思华年 #栈和排序#

#include <algorithm>
#include <climits>
#include <stack>
#include <vector>

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型vector 描述入栈顺序
     * @return int整型vector
     */
    vector<int> solve(vector<int>& a) {
        // write code here
        stack<int> s;
        //最后返回答案数组
        vector<int> ans;

        //bmax[i]数组记录的就是a数组第i位后面所剩余元素的最大值
        vector<int> bmax(a.size());

        bmax[a.size() - 1] = INT_MIN;//先让bmax数组的最后一个元素的值为无穷小
        //再从bamx数组倒数第二位开始填写
        for (int i = a.size() - 2; i >= 0; i--) {
            //倒序将bmax数组和a数组从最后一位开始进行逐位比较
            bmax[i] = max(a[i + 1], bmax[i + 1]); 
        }

        for (int i = 0; i < a.size(); i++) {
            //如果即将入栈的元素比后面还没入栈的元素中的最大值还要大，就说明这个元素是最大的
            if (a[i] > bmax[i]) {
                ans.push_back(a[i]);
                int last_max = bmax[i];//更新lastmax(用来记录后面还没入站的元素中的最大值)
                while (!s.empty() && s.top() > last_max) {
                    ans.push_back(s.top());
                    s.pop();
                }
            }
            //如果即将入栈的a数组的这个元素比后面剩余要入栈的元素中的最大值要小，直接入栈 
            else {
                s.push(a[i]);
            }
        }
        while (!s.empty()) {
            ans.push_back(s.top());
            s.pop();
        }

        return ans;
    }
};

基本算法思想：

1. 创建一个栈s和一个空的结果数组ans。

2. 创建一个辅助数组bmax，用来记录a数组的第i位后所剩余元素的最大值。

3. 初始化bmax的最后一个元素为INT_MIN（无穷小）。

4. 从倒数第二位开始遍历a数组，将bmax数组的每个元素设置为a数组从当前位置到末尾的最大值。

5. 遍历a数组，对于每个元素：

- 如果当前元素比后面还没入栈的元素中的最大值还要大，说明这个元素是最大的，将它加入ans数组。

同时，将栈中大于当前元素的元素都弹出，并加入ans数组。

- 如果当前元素比后面剩余要入栈的元素中的最大值要小，直接将它入栈。

6. 将栈中剩余的元素依次弹出，并加入ans数组。

7. 返回ans数组作为结果。

时间复杂度：

O(n)，其中n是a数组的长度。需要遍历a数组两次，分别是初始化bmax数组和遍历a数组。

空间复杂度：

O(n)，需要使用一个辅助数组bmax和一个栈s来辅助计算。