左边第一个比我大.cpp

/*
 * 题目：给定一个数组，要找到这个数组里面每个元素左边比我大的元素的位置
 * - 注意：是左边第一个比我大的，如果有多个的话
 * - 如果没有，那么用-1表示。
 *
 * 返回：一个数组，表示左边比我大的数的下标位置
 *
 * 输入：[5, 6]
 * 输出：[-1, -1]
 * 解释：A[0] = 5，左边比我大的元素没有, 所以记录为 = -1
 *       A[1] = 6, 左边比我大的元素为没有，所以记录为 = -1
 *       所以返回值是[-1, -1]
 */

class Solution {
  public:
    vector<int> findLeftLarge(vector<int>& A) {
        if (A.empty()) {
            return {};
        }
        const int N = A.size();

        // 结果数组
        vector<int> ans(N);

        // 注意，栈中的元素记录的是下标
        stack<int> t;

        // 注意这里的遍历方向发生了变化，因为我们是要找到左边比我小的元素的位置
        for (int i = N - 1; i >= 0; i--) {
            const int x = A[i];
            // 每个元素都遍历栈中的元素完成消除动作
            // 这里是递减栈
            // 如果发现进来的元素x与栈中元素相比
            // 如果大于栈中的元素，那么要把栈中的元素弹出去
            while (!t.empty() && A[t.top()] < x) {
                // 消除的时候，记录一下被谁消除了
                ans[t.top()] = i;
                // 消除时候，值更大的需要从栈中消失
                t.pop();
            }
            // 剩下的入栈
            t.push(i);
        }
        // 栈中剩下的元素，由于没有人能消除他们，因此，只能将结果设置为-1。
        while (!t.empty()) {
            ans[t.top()] = -1;
            t.pop();
        }

        return ans;
    }
};