962. Maximum Width Ramp

Version #2 Stack
Since we are looking for the maximum width between A[i] <= A[j]
We need the left to be as small as possible to match any potential right numbers
If a number is larger than its left value, it is useless for us, since it will never be the left part of our final result.
So our stack will become a decreasing array
After we add all the decreasing numbers to the stack, we iterate from the last element to the first element in our number array
We need our right number to be as large as possible
So we pop numbers from the stack for all numbers that less or equal to curr
We don't care any number that is smaller than current number because it has less chance to become larger than our potential left, and its index is smaller than our curr, so it will never become part of our final result

100.00 %
class Solution {
    public int maxWidthRamp(int[] A) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < A.length; i++) {
            if (stack.isEmpty() || A[i] < A[stack.peek()]) {
                stack.push(i);
            }
        }
        int max = 0;
        for (int i = A.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && A[i] >= A[stack.peek()]) {
                max = Math.max(max, i - stack.pop());
            }
        }
        return max;
    }
}

Version #1 Binary Search
O(nlogn)
85.71 %

class Solution {
    public int maxWidthRamp(int[] A) {
        // [6,0,8,2,1,5]
        // decreasing list of index
        List<Integer> list = new ArrayList<>();
        int max = 0;
        list.add(0);
        for (int i = 1; i < A.length; i++) {
            if (A[i] < A[list.get(list.size() - 1)]) {
                list.add(i);
            }
            int start = 0;
            int end = list.size() - 1;
            // current A[i]
            while (start < end) {
                int mid = start + (end - start) / 2;
                // System.out.println(A[list.get(mid)] + " " + A[i]);
                if (A[list.get(mid)] > A[i]) {
                    start = mid + 1;
                    // System.out.println(A[list.get(mid)] + " " + A[i]);
                } else {
                    end = mid;
                }
            }
            // System.out.println(A[list.get(start)] + " " + A[i]);
            if (A[list.get(start)] <= A[i]) {
                max = Math.max(max, i - list.get(start));
            }
        }
        return max;
    }
}