Max Special Product

You are given an array A containing N integers. The special product of each ith integer in this array is defined as the product of the following:<ul>

LeftSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (i>j). If multiple A[j]’s are present in multiple positions, the LeftSpecialValue is the maximum value of j. 

RightSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (j>i). If multiple A[j]s are present in multiple positions, the RightSpecialValue is the minimum value of j.

Write a program to find the maximum special product of any integer in the array.

Input: You will receive array of integers as argument to function.

Return: Maximum special product of any integer in the array modulo 1000000007.

Note: If j does not exist, the LeftSpecialValue and RightSpecialValue are considered to be 0.

Constraints 1 <= N <= 10^5 1 <= A[i] <= 10^9

思路:

用两个栈来帮助我们找到previous greater index(pgi)和next greater index(ngi)。
以A[1 5 2 4 3]为例，要找每个index的pgi，从index 0开始往右。
开始时栈为空[]，index 0的pgi为0，然后将index 0 push进栈。
index 1，栈为[0]，A[0] < 5，所以将0 pop，index 1的pgi同样为0，将index 1push。
index 2, 栈为[1]，A[1] > 2，所以index 2的pgi为1，将2 push。
index 3，栈为[2, 1]，A[2] < 4，pop栈, 栈为[1]，A[1] > 4，所以index 3的pgi为1，将3 push。
index 4，栈为[3, 1]，A[3] > 3，所以index 4的pgi为3。
我们所以得到pgi [0 0 1 1 3]，同样我们能得到ngi [1 0 3 0 0]，将两个array求max product，得到max special product为3。

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public int maxSpecialProduct(ArrayList<Integer> A) {
        /*
            1 5 2 4 3

            0 0 1 1 3
            1 0 3 0 0
        */
        int n = A.size();
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> lmax = new ArrayDeque<>();
        Deque<Integer> rmax = new ArrayDeque<>();
        for (int i = 0; i < n; i ++) {
            int v = A.get(i);
            while (lmax.size() > 0 && A.get(lmax.peek()) <= v) {
                lmax.pop();
            }
            if (lmax.size() == 0) {
                left[i] = 0;
            } else {
                left[i] = lmax.peek();
            }
            lmax.push(i);
        }
        for (int i = n - 1; i >= 0; i --) {
            int v = A.get(i);
            while (rmax.size() > 0 && A.get(rmax.peek()) <= v) {
                rmax.pop();
            }
            if (rmax.size() == 0) {
                right[i] = 0;
            } else {
                right[i] = rmax.peek();
            }
            rmax.push(i);
        }
        // System.out.println(Arrays.toString(left));
        // System.out.println(Arrays.toString(right));
        long max = 0;
        for (int i = 0; i < n; i ++) {
            max = Math.max(max, (long) left[i] * (long) right[i]);
        }
        return (int) (max % 1000000007);
    }
}