962. Maximum Width Ramp

T: O(n)
S: O(n)

class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty() || nums[stack.peek()] >= nums[i]) {
                stack.push(i);
            }
        }
        for (int j = n-1; j >= 0; j--) {
            while (!stack.isEmpty() && nums[stack.peek()] <= nums[j]) {
                int i = stack.pop();
                result = Math.max(result, j - i);
            }
        }
        return result;
    }
}
/**
T: O(n)
S: O(n)

0 1
0
1. 1

8
9


[9,8,1,0,1,9,4,0,4,1]

 9 9 9 9 9 9 4 4 4 1
             l
                   r
 */