मान लीजिए कि हमें संख्याओं की एक सूची और दूसरा मान k दिया गया है। इस बार हमारा कार्य सबसे लंबे अनुक्रम की लंबाई ज्ञात करना है जहां प्रत्येक आसन्न तत्व के बीच पूर्ण अंतर अधिकतम k है।
इसलिए, यदि इनपुट nums =[5, 6, 2, 1, −6, 0, −1, k =4 जैसा है, तो आउटपुट 6 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन अपडेट () को परिभाषित करें। इसमें i, x लगेगा
-
मैं :=मैं + एन
-
जबकि i गैर-शून्य है, करें
-
segtree[i] :=अधिकतम segtree[i], x
-
मैं :=मैं / 2
-
-
फ़ंक्शन क्वेरी () को परिभाषित करें। यह मैं, जम्मू ले जाएगा
-
उत्तर :=−अनंतता
-
मैं :=मैं + एन
-
जे:=जे + एन + 1
-
जबकि i
-
अगर मैं मॉड 2 1 के समान है, तो
-
उत्तर:=अधिकतम उत्तर, segtree[i]
-
मैं :=मैं + 1
-
-
अगर j mod 2 1 के समान है, तो
-
जे:=जे - 1
-
उत्तर:=अधिकतम उत्तर, segtree[j]
-
-
मैं :=मैं / 2
-
जे:=जे/2
-
-
वापसी उत्तर
-
अब, मुख्य कार्य में, निम्न कार्य करें -
-
अंक =[5, 6, 2, 1, −6, 0, −1]
-
कश्मीर =4
-
n =2 से घात (लघुगणक आधार 2 ((अंकों की लंबाई) + 1) + 1)
-
सेगट्री :=[0] * 100000
-
snums :=सूची संख्या क्रमित करें
-
अनुक्रमणिका :=एक संग्रह बनाएँ जहाँ x:i प्रत्येक अनुक्रमणिका के लिए i और तत्व x in (snums)
-
उत्तर :=0
-
अंकों में प्रत्येक x के लिए, करें
-
lo :=snums से बाईं ओर की स्थिति लौटाएं, जहां (x - k) क्रमबद्ध क्रम को बनाए रखते हुए डाला जा सकता है
-
hi :=(snums से सबसे बाईं ओर की स्थिति, जहां (x + k) क्रमबद्ध क्रम को बनाए रखते हुए डाला जा सकता है) - 1
-
गिनती:=क्वेरी (लो, हाय)
-
अद्यतन (सूचकांक [x], गिनती + 1)
-
उत्तर:=अधिकतम उत्तर, गिनती + 1
-
-
वापसी उत्तर
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
import math, bisect
class Solution:
def solve(self, nums, k):
n = 2 ** int(math.log2(len(nums) + 1) + 1)
segtree = [0] * 100000
def update(i, x):
i += n
while i:
segtree[i] = max(segtree[i], x)
i //= 2
def query(i, j):
ans = −float("inf")
i += n
j += n + 1
while i < j:
if i % 2 == 1:
ans = max(ans, segtree[i])
i += 1
if j % 2 == 1:
j −= 1
ans = max(ans, segtree[j])
i //= 2
j //= 2
return ans
snums = sorted(nums)
index = {x: i for i, x in enumerate(snums)}
ans = 0
for x in nums:
lo = bisect.bisect_left(snums, x − k)
hi = bisect.bisect_right(snums, x + k) − 1
count = query(lo, hi)
update(index[x], count + 1)
ans = max(ans, count + 1)
return ans
ob = Solution()
print(ob.solve([5, 6, 2, 1, −6, 0, −1], 4)) इनपुट
[5, 6, 2, 1, −6, 0, −1], 4
आउटपुट
6
