A ramp in an integer array nums is a pair (i, j) for which i &lt; j and nums[i] &lt;= nums[j]. The width of such a ramp is j - i.

Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.

&nbsp;
Example 1:

Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.


Example 2:

Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.


&nbsp;
Constraints:


	2 &lt;= nums.length &lt;= 5 * 104
	0 &lt;= nums[i] &lt;= 5 * 104


class Solution:
    def maxWidthRamp(self, nums: List[int]):
        st=[]
        n=len(nums)
        for i in range(n):
            if len(st)==0 or nums[st[-1]]>=nums[i]:
                st.append(i)
        print(st)
        max_idx=-1
        for j in range(n-1,-1,-1):
            while len(st) and nums[st[-1]]<=nums[j]:
                prev=st.pop()
                max_idx=max(max_idx,j-prev)

        return max_idx
class Solution {
    public int maxWidthRamp(int[] nums) {
        Stack<Integer> s = new Stack<>();
        int res = 0;
        for(int i = 0; i< nums.length; i++){
            if(!s.isEmpty() && nums[s.peek()]<=nums[i]) {
                res = Math.max(res, i-s.peek());
                continue;
            }
            s.push(i);
        }
        int i = nums.length-1;
        while(!s.isEmpty() && i>=0){
            if(nums[s.peek()]<=nums[i]){
                res = Math.max(res, i-s.peek());
                s.pop();
            }else{
                i--;
            }
        }
        return res;
    }
}
class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int n=nums.size();
        if(n==2){
            if(nums[0]<=nums[1])return 1;
            return 0;
        }
        stack<int>st;
        for(int i=0;i<n;i++){
            if(st.empty()||nums[i]<nums[st.top()]){st.push(i);}  // maintaining a monotonic decreasing stack
        }
        int ramp=0;
        for(int i=n-1;i>=0;i--){
            while(!st.empty() && nums[i]>=nums[st.top()] ){    
                ramp=max(ramp,i-st.top());
                st.pop();
            }
        }
        return ramp;
    }
};
var maxWidthRamp = function(nums) {
  let stack = [], ans = 0;
  for (let i = 0; i < nums.length; i++) {
    let index = lower_bound(stack, i);
    ans = Math.max(ans, i - index);
    if (!stack.length || nums[i] < nums[stack[stack.length - 1]]) stack.push(i);
  }
  return ans;
  
  function lower_bound(arr, index) {
    if (!arr.length) return index;
    let low = 0, high = arr.length - 1;
    while (low < high) {
      let mid = Math.floor((low + high) / 2);
      if (nums[arr[mid]] <= nums[index]) high = mid;
      else low = mid + 1;
    }
    return nums[arr[low]] <= nums[index] ? arr[low] : index;
  }
};
Maximum Width Ramp