使用堆栈

public static int[] maxLeftElement(int[] A)
{
    final int n = A.length;
    int[] ans = new int[n];

    Stack<Integer> S = new Stack<>();
    S.push(A[0]);

    for (int i = 0;i <  n;i++)
    {   
        if (S.peek() <= A[i]) 
        {
            S.pop();
            S.push(A[i]);
        }
        
        ans[i] = S.peek();
    }

    return ans;
}

高效解决方案

在上面的解决方案中，在函数的整个执行过程中，堆栈中只有一个元素。因此，很明显，堆栈没有提供任何好处。因此，最好用简单的int来替换它。

public static int[] maxLeftElement(int[] A)
{
    final int n = A.length;
    int[] ans = new int[n];

    int maxSoFar = A[0];
    for (int i = 0;i <  n;i++)
    {
        maxSoFar = Math.max(maxSoFar,A[i]);
        ans[i] = maxSoFar;
    }

    return ans;
}

直觉

对于每个A[i]，我们必须找到所有有效 i 的max(A[0..i])，如果考虑可能的元素，A[0..i]中可能只有一个max元素。
现在，令A[0..i]中的最大元素为maxSoFar，我们需要找到A[i+1]的最大左元素，即max(A[0...i+1])，简单地说，max(A[0..i+1]) = max(A[0...i],A[i+1]) = max(maxSoFar,A[i+1])可以在常数时间内求解。
我们已经知道A[0]的最大左元素是A[0]，所以，最初是maxSoFar = A[0]，因此，我们可以简单地为所有有效值不断增加i，并计算max(maxOfFar,A[i])。

为什么不堆叠？

当需要以特定的顺序存储许多元素时，应该使用堆栈，这可以帮助我们计算任何A[i]的答案。我们不需要在任何时刻跟踪多个元素来获得任何A[i]的答案。这排除了使用堆栈的可能性。