मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और k है। एक ऑपरेशन पर विचार करें जहां हम किसी एक तत्व को एक बार बढ़ा सकते हैं। यदि हम अधिकतम k बार ऑपरेशन कर सकते हैं, तो हमें समान तत्वों वाली सबसे लंबी सबलिस्ट ढूंढनी है।
उदाहरण के लिए, यदि इनपुट nums = [3, 5, 9, 6, 10, 7] और k = 6 है, तो आउटपुट 3 होगा, क्योंकि हम 9 को एक बार और 6 को चार बार बढ़ाकर सबलिस्ट [10, 10, 10] प्राप्त कर सकते हैं।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
यदि
numsखाली है, तो 0 लौटाएं।wMaxकोnumsके आकार का एक डबल-एंडेड क्यू बनाएं और(nums[0], 0)डालें।i := 0,inc := 0आरंभ करें।jको 1 सेlen(nums) - 1तक लूप में चलाएं:जब तक
wMaxखाली नहीं है औरwMax[0][1] < i, बाएं तत्व को हटाएं।pMax := wMax[0][0]प्राप्त करें।जब तक
wMaxखाली नहीं है औरwMax[-1][0] <= nums[j], दाएं तत्व को हटाएं।(nums[j], j)कोwMaxके अंत में जोड़ें।यदि
pMax < wMax[0][0], तोinc += (j - i) * (wMax[0][0] - pMax)।अन्यथा,
inc += pMax - nums[j]।यदि
inc > k, तो:inc -= wMax[0][0] - nums[i]।जब तक
wMaxखाली नहीं है औरwMax[0][1] <= i, बाएं तत्व को हटाएं।यदि
wMax[0][0] < nums[i], तोinc -= (nums[i] - wMax[0][0]) * (j - i)।i := i + 1बढ़ाएं।
len(nums) - iलौटाएं।
उदाहरण
from collections import deque class Solution: def solve(self, nums, k): if not nums: return 0 wMax = deque([(nums[0], 0)], maxlen=len(nums)) i = 0 inc = 0 for j in range(1, len(nums)): while wMax and wMax[0][1] < i: wMax.popleft() pMax = wMax[0][0] while wMax and wMax[-1][0] <= nums[j]: wMax.pop() wMax.append((nums[j], j)) if pMax < wMax[0][0]: inc += (j - i) * (wMax[0][0] - pMax) else: inc += pMax - nums[j] if inc > k: inc -= wMax[0][0] - nums[i] while wMax and wMax[0][1] <= i: wMax.popleft() if wMax[0][0] < nums[i]: inc -= (nums[i] - wMax[0][0]) * (j - i) i += 1 return len(nums) - i ob = Solution() nums = [3, 5, 9, 6, 10, 7] k = 6 print(ob.solve(nums, k))
इनपुट
[3, 5, 9, 6, 10, 7], 6
आउटपुट
3
