Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j].  The width of such a ramp is j - i.
Find the maximum width of a ramp in A.  If one doesn't exist, return 0.
 
Example 1:
Input: [6,0,8,2,1,5]
Output: 4
Explanation: 
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.


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




 
Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Starter code: class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		width = 0
		icandidate = [0]
		for i in range(len(A)):
			if A[i] < A[icandidate[-1]]:
				icandidate.append(i)
		for j in range(len(A) - 1, -1, -1):
			while icandidate and A[icandidate[-1]] <= A[j]:
				width = max(width, j - icandidate.pop())
		return width


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		stack = []
		n = len(A)
		for i in range(n):
			if not stack or A[stack[-1]] > A[i]:
				stack.append(i)
		res = 0
		i = n - 1
		while i > res:
			while stack and A[stack[-1]] <= A[i]:
				res = max(res, i - stack[-1])
				stack.pop()
			i -= 1
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		sorted_indices = sorted(list(range(len(A))), key=lambda x: A[x])
		minimum_index = sorted_indices[0]
		answer = 0
		for i in range(1, len(sorted_indices)):
			if sorted_indices[i] > minimum_index:
				answer = max(answer, sorted_indices[i] - minimum_index)
			else:
				minimum_index = sorted_indices[i]
		return answer


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		n = len(A)
		idx = sorted(range(n), key=A.__getitem__)
		i = n
		result = 0
		for j in idx:
			result = max(result, j - i)
			i = min(i, j)
		return result


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		idxs = sorted(range(len(A)), key=lambda i: A[i])
		ramp = 0
		mini = len(A)
		for idx in idxs:
			mini = min(mini, idx)
			ramp = max(ramp, idx - mini)
		return ramp


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		(stack, ret) = ([], 0)
		for (i, a) in enumerate(A):
			if not stack or A[stack[-1]] > a:
				stack.append(i)
		for i in reversed(range(len(A))):
			while stack and A[stack[-1]] <= A[i]:
				ret = max(ret, i - stack.pop())
		return ret


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		a = sorted(list(range(len(A))), key=lambda x: A[x])
		ans = 0
		m = float('inf')
		for i in a:
			ans = max(ans, i - m)
			m = min(m, i)
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		n = len(A)
		rightMax = [0 for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			rightMax[i] = max(rightMax[i + 1], A[i])
		i = 0
		j = 0
		result = 0
		while i < n and j < n:
			if A[i] <= rightMax[j]:
				result = max(result, j - i)
				j += 1
			else:
				i += 1
		return result


from operator import itemgetter

class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		B = [(i, A[i]) for i in range(0, len(A))]
		B.sort(key=itemgetter(1))
		curminidx = B[0][0]
		res = 0
		for i in range(1, len(A)):
			curidx = B[i][0]
			if curidx < curminidx:
				curminidx = curidx
			else:
				res = max(res, curidx - curminidx)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		st_i = [a for (a, _) in sorted(enumerate(A), key=lambda a: a[-1])]
		mi = math.inf
		mx = -math.inf
		for idx in st_i:
			mi = min(idx, mi)
			mx = max(mx, idx - mi)
		return mx


class Solution(object):

	def maxWidthRamp(self, A):
		ans = 0
		m = float('inf')
		for i in sorted(range(len(A)), key=A.__getitem__):
			ans = max(ans, i - m)
			m = min(m, i)
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		largest = 0
		A = [(index, value) for (index, value) in enumerate(A)]
		A.sort(key=lambda x: x[1])
		minimum = float('inf')
		for (index, el) in A:
			largest = max(largest, index - minimum)
			minimum = min(index, minimum)
		return largest


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		stack = []
		for (i, v) in enumerate(A):
			if i == 0 or v < A[stack[-1]]:
				stack.append(i)
		ans = 0
		for i in range(len(A) - 1, -1, -1):
			while stack and A[i] >= A[stack[-1]]:
				ans = max(ans, i - stack.pop())
		return ans


class Solution:

	def maxWidthRamp(self, A):
		sorted_idx = [x[0] for x in sorted(enumerate(A), key=lambda x: x[1])]
		res = 0
		min_idx = sorted_idx[0]
		for idx in sorted_idx:
			res = max(res, idx - min_idx)
			min_idx = min(min_idx, idx)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		arr = [(a, i) for (i, a) in enumerate(A)]
		arr.sort()
		(imin, res) = (float('inf'), 0)
		for (_, i) in arr:
			res = max(res, i - imin)
			imin = min(imin, i)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		stack = []
		for (i, val) in enumerate(A):
			if not stack or val < A[stack[-1]]:
				stack.append(i)
		maxWidth = 0
		for i in range(len(A) - 1, -1, -1):
			val = A[i]
			while stack and val >= A[stack[-1]]:
				maxWidth = max(maxWidth, i - stack.pop())
		return maxWidth


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		arr = [(a, i) for (i, a) in enumerate(A)]
		arr.sort()
		(imax, res) = (float('-inf'), 0)
		for (_, i) in reversed(arr):
			res = max(res, imax - i)
			imax = max(imax, i)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		n = len(A)
		arr = sorted([(a, i) for (i, a) in enumerate(A)])
		rindex = [0] * n
		rindex[-1] = arr[-1][1]
		for i in range(n - 2, -1, -1):
			rindex[i] = max(arr[i][1], rindex[i + 1])
		mx = 0
		for i in range(n):
			mx = max(mx, rindex[i] - arr[i][1])
		return mx


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		ans = {}
		for i in range(len(A)):
			if A[i] in list(ans.keys()):
				ans[A[i]].append(i)
			else:
				ans[A[i]] = [i]
		B = sorted(A, reverse=True)
		max_index = -1
		ramp = 0
		for key in B:
			l = max_index - ans[key][0]
			ramp = max(ramp, l)
			max_index = max(max_index, ans[key][len(ans[key]) - 1])
		return ramp


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		ans = 0
		l = [(n, i) for (i, n) in enumerate(A)]
		l.sort()
		mini = float('inf')
		for e in l:
			mini = min(mini, e[1])
			ans = max(ans, e[1] - mini)
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		A_idx = []
		for (idx, a) in enumerate(A):
			A_idx.append((a, idx))
		A_idx_sorted = sorted(A_idx, key=lambda x: x[0])
		mn = float('inf')
		res = 0
		for (a, idx) in A_idx_sorted:
			res = max(res, idx - mn)
			mn = min(mn, idx)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		val_pos_list = [(value, pos) for (pos, value) in enumerate(A)]
		val_pos_list.sort()
		rightmost = len(A) - 1
		visited_pos = set()
		result = 0
		for (value, pos) in val_pos_list:
			while rightmost in visited_pos:
				rightmost -= 1
			distance = max(0, rightmost - pos)
			result = max(result, distance)
			visited_pos.add(pos)
		return result


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		n = len(A)
		(minLeft, maxRight) = ([A[0]] * n, [A[-1]] * n)
		for i in range(1, n):
			minLeft[i] = min(minLeft[i - 1], A[i])
			maxRight[n - i - 1] = max(maxRight[n - i], A[n - i - 1])
		i = j = n - 1
		res = 0
		while i >= 0 and j >= 0:
			if minLeft[i] <= maxRight[j]:
				res = max(res, j - i)
				i -= 1
			else:
				j -= 1
		return res


class Solution:

	def find_right_max(self, arr):
		right_max = [arr[-1]]
		for i in range(len(arr) - 2, -1, -1):
			right_max.append(max(arr[i], right_max[-1]))
		return reversed(right_max)

	def maxWidthRamp(self, A: List[int]) -> int:
		indices_sort = [i[0] for i in sorted(enumerate(A), key=lambda x: x[1])]
		set_ele = set(A)
		indices = []
		for idx in indices_sort:
			if idx in set_ele:
				indices.append(idx)
		right_max = self.find_right_max(indices_sort)
		max_width_ramp = float('-inf')
		for (idx, right_max) in zip(indices_sort, right_max):
			max_width_ramp = max(right_max - idx, max_width_ramp)
		return max_width_ramp


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		Aindex = [(a, i) for (i, a) in enumerate(A)]
		Aindex.sort(key=lambda x: (x[0], x[1]))
		mn = len(A)
		ans = 0
		for (a, i) in Aindex:
			ans = max(ans, i - mn)
			mn = min(mn, i)
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		collections = {}
		for (i, el) in enumerate(A):
			if el in collections:
				collections[el][1] = i
			else:
				collections[el] = [i, i]
		sorted_collections = sorted(collections.keys())
		for i in range(1, len(sorted_collections)):
			(left, right) = (i, len(sorted_collections) - i - 1)
			collections[sorted_collections[left]][0] = min(collections[sorted_collections[left]][0], collections[sorted_collections[left - 1]][0])
			collections[sorted_collections[right]][1] = max(collections[sorted_collections[right]][1], collections[sorted_collections[right + 1]][1])
		result = 0
		for el in collections.values():
			result = max(result, el[1] - el[0])
		return result


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		ind = [i for i in range(len(A))]
		(A, ind) = zip(*sorted(zip(A, ind)))
		m = len(A) - 1
		ans = 0
		for i in range(len(A)):
			ans = max(ind[i] - m, ans)
			m = min(ind[i], m)
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		minHeap = [(A[i], i) for i in range(len(A))]
		heapq.heapify(minHeap)
		maxWidth = 0
		(minVal, minPos) = heapq.heappop(minHeap)
		while minHeap:
			(val, pos) = heapq.heappop(minHeap)
			if val >= minVal:
				maxWidth = max(maxWidth, pos - minPos)
			if pos < minPos:
				minVal = val
				minPos = pos
		return maxWidth


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		left = [A[0]]
		right = [A[-1]]
		for i in range(1, len(A)):
			left.append(min(A[i], left[i - 1]))
			right.append(max(A[len(A) - 1 - i], right[-1]))
		right = right[::-1]
		pt_l = 0
		pt_r = 0
		ans = 0
		while pt_r < len(A):
			if left[pt_l] <= right[pt_r]:
				ans = max(ans, pt_r - pt_l)
				pt_r += 1
			else:
				pt_l += 1
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		descends = [(A[0], 0)]

		def bs(t):
			(lo, hi) = (0, len(descends) - 1)
			while lo < hi:
				mid = (lo + hi) // 2
				if descends[mid] > t:
					lo = mid + 1
				else:
					hi = mid
			return lo
		rint = 0
		for i in range(1, len(A)):
			if A[i] < descends[-1][0]:
				descends.append((A[i], i))
			else:
				left = bs((A[i], i))
				rint = max(rint, i - descends[left][1])
		return rint


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		(idxsMin, res) = ([], 0)
		for (i, x) in enumerate(A):
			if not idxsMin or A[idxsMin[-1]] > x:
				idxsMin.append(i)
		for j in range(len(A))[::-1]:
			while idxsMin and A[idxsMin[-1]] <= A[j]:
				res = max(res, j - idxsMin.pop())
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		n = len(A)
		l = []
		res = 0
		for j in range(n):
			if not l or A[l[-1]] > A[j]:
				l.append(j)
			else:
				(left, right) = (0, len(l) - 1)
				while left < right:
					mid = (left + right) // 2
					if A[l[mid]] <= A[j]:
						right = mid
					else:
						left = mid + 1
				res = max(res, j - l[left])
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		stack = []
		ans = 0
		for (i, a) in enumerate(A):
			if not stack or stack[-1][0] > a:
				stack.append((a, i))
			else:
				(l, r) = (0, len(stack) - 1)
				while l < r:
					m = (r + l) // 2
					if stack[m][0] > a:
						l = m + 1
					else:
						r = m
				if stack[l][0] <= a:
					ans = max(ans, i - stack[l][1])
		return ans


class Solution:

	def maxWidthRamp(self, x: List[int]) -> int:
		ma = 0
		l = len(x)
		st = [(x[0], 0)]
		for i in range(l):
			if x[i] < st[-1][0]:
				st.append((x[i], i))
		for i in range(l - 1, -1, -1):
			while st != [] and x[i] >= st[-1][0]:
				(a, b) = st.pop(-1)
				ma = max(i - b, ma)
			if st == []:
				break
		return ma


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		n = len(A)
		stack = []
		for (i, num) in enumerate(A):
			if not stack or num < A[stack[-1]]:
				stack.append(i)
		ans = 0
		for j in range(n - 1, -1, -1):
			while stack and A[j] >= A[stack[-1]]:
				ans = max(ans, j - stack.pop())
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		mx = 0
		ind = float('inf')
		index = collections.defaultdict(list)
		for (i, x) in enumerate(A):
			index[x].append(i)
		print(index)
		for num in sorted(A):
			mx = max(mx, index[num][-1] - ind)
			ind = min(ind, index[num][0])
		return mx


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		stack = []
		res = 0
		for (i, a) in enumerate(A):
			if stack and A[stack[-1]] <= a:
				j = len(stack) - 1
				while j >= 0 and A[stack[j]] <= a:
					res = max(res, i - stack[j])
					j -= 1
			else:
				stack.append(i)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		record = [[A[i], i] for i in range(len(A))]
		record.sort(key=lambda x: [x[0], x[1]])
		res = 0
		pre_min = record[0][1]
		for i in range(1, len(A)):
			pre_min = min(pre_min, record[i][1])
			res = max(res, record[i][1] - pre_min)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		N = len(A)
		stack = []
		res = 0
		for (i, a) in enumerate(A):
			if not stack or stack[-1][1] > a:
				stack.append((i, a))
			else:
				x = len(stack) - 1
				while x >= 0 and stack[x][1] <= a:
					res = max(res, i - stack[x][0])
					x -= 1
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		N = 50001
		sms = [None] * N
		lgs = [None] * N
		for (i, x) in enumerate(A):
			if sms[x] is None:
				sms[x] = i
			lgs[x] = i
		m = 0
		ss = float('inf')
		for x in range(N):
			if lgs[x] is None:
				continue
			ss = min(ss, sms[x])
			m = max(m, lgs[x] - ss)
		return m


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		(stack, ans) = ([], 0)
		for (i, val) in enumerate(A):
			if not stack or A[stack[-1]] > val:
				stack.append(i)
		for j in reversed(list(range(len(A)))):
			while stack and A[stack[-1]] <= A[j]:
				ans = max(ans, j - stack.pop())
		return ans


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		numbers = list(((num, i) for (i, num) in enumerate(A)))
		numbers.sort()
		max_gap = 0
		min_element = numbers[0][1]
		for i in range(1, len(A)):
			min_element = min(min_element, numbers[i][1])
			max_gap = max(max_gap, numbers[i][1] - min_element)
		return max_gap


class Solution:

	def maxWidthRamp(self, a: List[int]) -> int:
		sis = sorted(list(range(len(a))), key=a.__getitem__)
		return max((i - m for (m, i) in zip(itertools.accumulate(sis, min), sis)))


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		(min_map, max_map) = ({}, {})
		for (i, v) in enumerate(A):
			min_map[v] = min(i, min_map.get(v, i))
			max_map[v] = max(i, max_map.get(v, i))
		min_idx = None
		res = 0
		for i in range(0, 50001):
			if i not in min_map:
				continue
			if min_idx is None:
				min_idx = min_map[i]
			else:
				min_idx = min(min_idx, min_map[i])
			if max_map[i] > min_idx:
				res = max(res, max_map[i] - min_idx)
		return res


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		helper = []
		for (i, x) in enumerate(A):
			helper.append((x, i))
		helper.sort(key=lambda x: x[0])
		imin = helper[0][1]
		maxlen = 0
		for (val, indx) in helper:
			if indx >= imin:
				maxlen = max(maxlen, indx - imin)
			imin = min(imin, indx)
		return maxlen


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		(stack, n) = ([], len(A))
		maxy = 0
		i = 0
		for (i, v) in enumerate(A):
			if not stack or v < stack[-1][0]:
				stack.append((v, i))
				continue
			j = -1
			while j >= -1 * len(stack) and v >= stack[j][0]:
				maxy = max(maxy, i - stack[j][1])
				j -= 1
		return maxy


class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		preList = [0]
		ALen = len(A)
		for i in range(1, ALen):
			if A[i] < A[preList[-1]]:
				preList.append(i)
		ans = 0
		preR = len(preList) - 1
		for i in range(ALen - 1, -1, -1):
			l = 0
			while preR > 0 and preList[preR] >= i:
				preR -= 1
			r = preR
			if A[i] < A[preList[l]] and A[i] >= A[preList[r]]:
				while r > l:
					m = (r + l) // 2
					if A[preList[m]] < A[i]:
						r = m
					elif A[preList[m]] > A[i]:
						l = m + 1
					else:
						l = m
						r = m - 1
				ans = max(ans, i - preList[l])
			elif A[i] >= A[preList[l]]:
				ans = max(ans, i - preList[l])
		return ans


from sortedcontainers import SortedList

class Solution:

	def maxWidthRamp(self, A: List[int]) -> int:
		li = list()
		for (i, n) in enumerate(A):
			li.append((n, i))
		li.sort()
		ans = 0
		bt = SortedList()
		for pair in li:
			n = pair[0]
			i = pair[1]
			if len(bt) == 0:
				bt.add(i)
				continue
			if bt[0] < i:
				if i - bt[0] > ans:
					ans = i - bt[0]
			bt.add(i)
		return ans