পাইথনে একটি নাম্বার লিস্ট nums দেওয়া আছে। লিস্টের সব পিক এলিমেন্টের (peak element) ইনডেক্স খুঁজে বের করতে হবে, অ্যাসেন্ডিং ক্রমে। একটি ইনডেক্স i পিক এলিমেন্ট হবে যদি নিচের তিনটি শর্ত সফল হয়:
- ডান পাশে
nums[i]-এর থেকে ভিন্ন প্রথম সংখ্যা না থাকলে অথবা সেটিnums[i]-এর চেয়ে ছোট হলে - বাম পাশে
nums[i]-এর থেকে ভিন্ন প্রথম সংখ্যা না থাকলে অথবা সেটিnums[i]-এর চেয়ে ছোট হলে - বাম বা ডান পাশে কমপক্ষে একটি সংখ্যা আছে যা
nums[i]-এর থেকে ভিন্ন
উদাহরণ
ইনপুট: nums = [5, 8, 8, 8, 6, 11, 11]
আউটপুট: [1, 2, 3, 5, 6]
ব্যাখ্যা: ৮-এর প্ল্যাটো (plateau) ইনডেক্স ১, ২, ৩ পিক হিসেবে গণ্য হয়েছে। ১১-এর প্ল্যাটো ইনডেক্স ৫, ৬ পিক হিসেবে গণ্য হয়েছে।
এলগরিদম
n = len(nums),ans = [],i = 0- যখন
i < n:i0 = i(প্ল্যাটোর শুরু)- যখন
i < nএবংnums[i] == nums[i0]:i += 1(প্ল্যাটোর শেষ খুঁজুন) - শর্ত চেক করুন:
- বাম পাশ:
i0 == 0বাnums[i0] > nums[i0-1] - ডান পাশ:
i == nবাnums[i0] > nums[i] - নন-ফ্ল্যাট:
i0 != 0বাi != n(কমপক্ষে এক পাশে ভিন্ন মান আছে)
- বাম পাশ:
- যদি সব সত্য হয়:
ans.extend(range(i0, i))(পুরো প্ল্যাটোর ইনডেক্স যোগ করুন)
ansরিটার্ন করুন
পাইথন ইমপ্লিমেন্টেশন
def solve(nums):
n = len(nums)
ans = []
i = 0
while i < n:
i0 = i
while i < n and nums[i] == nums[i0]:
i += 1
if (i0 == 0 or nums[i0] > nums[i0 - 1]) and (i == n or nums[i0] > nums[i]):
if i0 != 0 or i != n:
ans.extend(range(i0, i))
return ans
nums = [5, 8, 8, 8, 6, 11, 11]
print(solve(nums)) # Output: [1, 2, 3, 5, 6]ইনপুট
[5, 8, 8, 8, 6, 11, 11]আউটপুট
[1, 2, 3, 5, 6]ব্যাখ্যা
- প্ল্যাটো হ্যান্ডলিং: একই মানের רציפה সিকোয়েন্স (যেমন ৮,৮,৮) কে একটি প্ল্যাটো হিসেবে বিবেচনা করা হয়। পুরো প্ল্যাটোই পিক হয় যদি এর দু পাশে ছোট মান থাকে।
- এজ কেস: শুরুতে বা শেষে প্ল্যাটো হলে শুধু এক পাশ চেক করা হয়।
- ফ্ল্যাট লিস্ট এড়ানো: শর্ত ৩ নিশ্চিত করে যে পুরো লিস্ট একই মান হলে কোনো পিক নেই।
সময় জটিলতা
O(n) — প্রতিটি এলিমেন্ট একবারই ভিজিট হয়। স্পেস: O(1) অতিরিক্ত (আউটপুট বাদে)।
এই অ্যালগরিদমটি প্ল্যাটো-সহ পিক ডিটেকশনের জন্য স্ট্যান্ডার্ড এবং দক্ষ।
