問題：給定一個整數陣列 A，找出受 A[i] <= A[j] 約束的 j - i 的最大值。
如果沒有可能的解決方案，則回傳 -1。
例子 ：
A : [3 5 4 2] 輸出: 2 對 (3, 4)
輸入： 9 8 7 -9 -1
預期產出： 1
我的輸出： 0
除了上面給出的輸入之外，我嘗試的代碼在所有情況下都運行，誰能解釋為什么它在這種情況下失敗并為我提供更正的版本？
我的代碼（Python）：
class Solution:
def maximumGap(self, A):
# write your method here
m=-1
for i in range(len(A)-1):
j=len(A)-i-1
if(A[i]<=A[j]):
m=max(m,j-i)
return m
我嘗試使用 2 個回圈，它通過了上述情況，但為另一個回圈提供了 Time Limit Exceed。
m=-1
for i in range(len(A)):
for j in range(len(A)):
if(A[i]<=A[j]):
m=max(m,j-i)
return m
uj5u.com熱心網友回復：
您不需要測驗每一對。從最后搜索直到找到一個元素是>=當前元素，這將是最大的差距。
作為額外的優化，您可以保存該j元素的值，并在超過它時跳出外部回圈。
m = -1
maxj = len(A)
for i, el in enumerate(A):
if i > maxj:
break
for j in range(len(A)-1, -1, -1):
if el <= A[j]:
m = max(m, j-i)
maxj = j
break
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/363092.html
上一篇：我有一個關于內部函式的問題