給定一個nums長度n為的整數陣列，對于每個索引i，我試圖找到最右邊的索引j，使得i < j和nums[j] >= nums[i]。這個問題有 O(N) 解決方案嗎？我知道可以用于此類問題的單調堆疊，但無法推匯出演算法。
例如，給定一個陣列 A:
A = [9,8,1,0,1,9,4,0,4,1]，解應該輸出
[5,5,9,9,9,-1,8,9,-1,-1]。這里-1表示沒有索引滿足約束。
此鏈接問了同樣的問題，接受的答案僅適用于 O(NlogN)。我想知道 O(N) 解決方案是否可行。
謝謝你。
更新
基于@Aivean 的回答，這里是Python 中的O(Nlog(N))解決方案。
def rightmostGreaterOrEqual(nums):
A, n = nums, len(nums)
indx = [-1]*n
stack, stackv = [], []
for i in range(n-1, -1, -1):
if not stack or nums[stack[-1]] < nums[i]:
stack.append(i)
stackv.append(nums[i])
else:
idx = bisect.bisect_left(stackv, nums[i])
indx[i] = stack[idx]
return indx
B = [9,8,1,0,1,9,4,0,4,1]
rightGreat = rightmostGreaterOrEqual(B)
print(B)
[9, 8, 1, 0, 1, 9, 4, 0, 4, 1]
print(rightGreat)
[5, 5, 9, 9, 9, -1, 8, 9, -1, -1]
uj5u.com熱心網友回復：
對于所寫的問題，不會有 O(N) 演算法。給定一個解決此問題的函式，您可以使用它將 N/2 個任意數字劃分為 N/2 個任意相鄰范圍。
例如[2532,1463,3264,200,4000,3000,2000,1000]產生[5,6,4,7,-1,-1,-1,-1]，識別第N/ 2個數字。
如果您只能通過比較來關聯數字，那么這將花費您 N/2 * log(N/2) 次比較，因此 O(N log N) 時間。
如果沒有對數字大小的限制，這會讓您像基數排序一樣作弊，那么不會有比所有基于比較的方法漸近更快的方法。
uj5u.com熱心網友回復：
由于 的附加約束，為給定找到最左邊和最右邊 的兩個問題是不對稱的。當我在談論這兩個任務我認為約束是不翻轉。這種約束手段，我們始終著眼于正確的搜索時，我們是否正在尋找最右邊或左邊。如果沒有這個約束，兩個任務將是對稱的。jii < ji < jij j
1. 找到最右邊的 j，使得i < j和nums[i] ≤ nums[j]
解決此任務的一種方法是nums從右向左遍歷并維護已訪問元素（及其索引）的嚴格遞增子序列。僅當當前元素大于序列中已存在的最大元素時，才會將其添加到序列中。向序列中添加新元素是 O(1)。
對于每個元素，nums您必須在訪問過的元素的子序列中執行二分查找，以找到大于或等于當前元素的值。二分查找是 O(log n)。
總時間為O(n log n)，所需的輔助空間為O(n)。
這是問題的圖形表示：
這里的黃點代表形成嚴格遞增序列的元素（它們answer將是 -1）。每隔一個元素（藍色）選擇由黃色元素形成的范圍之一。
2. 找到最左邊的j，使得i < j和nums[i] ≤ nums[j]
與前一個問題相反，這個問題可以使用單調堆疊在 O(n) 時間和 O(n) 空間內解決。與上一個問題類似，當您nums從右向左遍歷時，您會形成并維護一個單調堆疊，但重要的是，當新元素添加到堆疊時，所有較小的元素都會從堆疊中洗掉。而不是使用二分查找來查找較大的元素，答案就在堆疊的新頂部（在洗掉所有較小的元素之后）。這使得更新堆疊并為每個元素找到答案分攤 O(1)。
此處黃色元素表示具有 的元素answer = -1，當它們被添加到堆疊中時，它們完全清空了堆疊，因為它們比堆疊中的所有其他元素都大。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/340799.html
下一篇：PHP如何組合陣列并創建新陣列