I'm trying to find the max element to the left of each element but i could write code for only the first 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);
    }

CodePudding user response：

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;
}

Efficient Solution

In the above solution, there will be only one element in the stack throughout the execution of the function. Hence, it is quite clear to observe the stack does not offer any benefit whatsoever. Hence, it is better to replace it with a simple 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;
}

Intuition

For each A[i], we have to find max(A[0..i]), for all the valid i. If we think about the possible element, there could be only one max element in A[0..i].

Now, let the max element in A[0..i] is maxSoFar. We need to find the max left element for A[i 1], which will be max(A[0...i 1]). Trivially, max(A[0..i 1]) = max(A[0...i],A[i 1]) = max(maxSoFar,A[i 1]) which can be solved in constant time.

We already know max left element for A[0] will be A[0]. So, initially maxSoFar = A[0]. Hence, we can simple keep increasing i for all the valid values and compute max(maxOfFar,A[i]).

Why not stack?

Stack should be used when there is a need to store many elements in a particular order which can help us compute the answer for any A[i]. We do not need to keep track of multiple elements at any instant to obtain the answer for any A[i] for the problem in question. This rules out the possibility of using stack.