查找数组中每个元素左边的最大元素(不是第一个最大值)

Question

我试图找到每个元素左侧的最大元素，但我只能为第一个max编写代码。

public static void main(String[] args) {
int a[]={3,0,0,2,0,4};
Stack<Integer> st=new Stack<Integer>();
ArrayList<Integer> al=new ArrayList<>();
for(int i=0;i<5;i++){
while(st.size()>0 && a[st.peek()]<a[i]){
st.pop();
}
if(st.empty()) al.add(a[i]);
else al.add(a[st.peek()]);
st.push(i);
}
System.out.println(al);
}

Answer 1

Using Stack

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]，我们必须找到max(A[0..i])，对于所有有效的i。如果我们考虑可能的元素，A[0..i]中可能只有一个最大元素。

现在，设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])。

为什么不堆叠?

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