【题解】 栈和排序（栈 + 预处理 / 贪心）

https://www.nowcoder.com/practice/95cb356556cf430f912e7bdf1bc2ec8f?tpId=196&tqId=37173&ru=/exam/oj

1. 预处理最大值

#include <climits> // 包含标准整数类型的定义
#include <vector>  // 包含标准vector容器的定义

class Solution {
  public:
    /**
    * 栈排序算法实现
    * @param a int整型vector 描述入栈顺序
    * @return int整型vector 排序后的栈
    */
    vector<int> solve(vector<int>& a) {
        // 定义栈和右端点的最大值数组
        int n = a.size(); // 栈的大小
        stack<int> st;    // 定义一个整型栈
        vector<int> right(n, 0); // 初始化右端点数组，所有元素初始为0
        right[n - 1] = INT_MIN; // 将最后一个元素设置为最小整数值，作为初始值
        // 计算每个位置的右端点最大值
        for (int i = n - 2; i >= 0; --i) {
            right[i] = max(right[i + 1], a[i + 1]);
        }

        vector<int> ret; // 定义返回结果的vector
        // 遍历入栈序列，按照规则排序
        for (int i = 0; i < n; ++i) {
            if (a[i] > right[i]) { // 如果当前元素大于其右端点的最大值
                ret.push_back(a[i]); // 将当前元素加入返回结果
                int lastMax = right[i]; // 记录当前元素作为下一个比较的基准
                // 弹出所有比基准值大的栈顶元素
                while (!st.empty() && st.top() > lastMax) {
                    ret.push_back(st.top()); // 弹出并加入返回结果
                    st.pop(); // 弹出栈顶元素
                }
            } else {
                st.push(a[i]); // 如果当前元素小于或等于其右端点的最大值，则压入栈中
            }
        }
        // 弹出栈中剩余的所有元素
        while (!st.empty()) {
            ret.push_back(st.top());
            st.pop();
        }

        return ret; // 返回排序后的栈
    }
};

2. 贪心

class Solution {
public:
    /**
     * 栈排序算法实现
     * @param a int整型vector 描述入栈顺序
     * @ @return int整型vector 排序后的栈
     */
    vector<int> solve(vector<int>& a) {
        // 定义栈和哈希表，哈希表用于记录元素是否已经入栈
        int n = a.size();
        stack<int> st;
        bool hash[50010] = {0}; // 假设元素的值不会超过50000，初始化哈希表
        int aim = n; // aim用于记录当前需要出栈的元素的索引
        vector<int> ret; // 定义返回结果的vector

        // 遍历输入的栈序列
        for (auto x : a) {
            st.push(x); // 将元素压入栈中
            hash[x] = true; // 记录该元素已经入栈

            // 更新aim值，即找到下一个未入栈的元素的索引
            while (hash[aim]) {
                aim--; // 如果当前aim位置的元素已经入栈，则aim减1
            }

            // 出栈操作
            while (st.size() && st.top() >= aim) {
                ret.push_back(st.top()); // 弹出栈顶元素，并加入结果vector
                st.pop(); // 弹出栈顶元素
            }
        }

        return ret; // 返回排序后的栈序列
    }
};