পাইথনে সমুদ্র দেখা যাবে এমন বিল্ডিং খুঁজে বের করা

বিল্ডিং হাইটস লিস্ট দেওয়া আছে। একটি বিল্ডিং সমুদ্র দেখতে পাবে যদি তার ডান পাশের সব বিল্ডিং তার চেয়ে ছোট হয়। যেসব ইনডেক্স থেকে সমুদ্র দেখা যায় সেগুলো এসেন্ডিং অর্ডারে রিটার্ন করুন।

ইনপুট উদাহরণ

heights = [8, 12, 12, 9, 10, 6]

আউটপুট: [2, 4, 5] (ইনডেক্স ২: হাইট ১২, ইনডেক্স ৪: হাইট ১০, ইনডেক্স ৫: হাইট ৬)

অ্যালগরিদম

মনোটোনিক স্ট্যাক ব্যবহার করুন। বাম থেকে ডানে ট্রাভার্স করুন: করেন্ট হাইট >= স্ট্যাকের টপ হাইট হলে পপ করুন। তারপর করেন্ট ইনডেক্স পুশ করুন। স্ট্যাকে থাকা ইনডেক্সগুলোই আন্স।

পাইথন কোড

def solve(heights):
    stack = []
    for idx, h in enumerate(heights):
        while stack and heights[stack[-1]] <= h:
            stack.pop()
        stack.append(idx)
    return stack

# টেস্ট
print(solve([8, 12, 12, 9, 10, 6]))  # [2, 4, 5]

ব্যাখ্যা

স্ট্যাকে স্ট্রিক্টলি ডিক্রিজিং হাইটের ইনডেক্স থাকে। নতুন বিল্ডিং আসলে পুরনো ছোট বিল্ডিংগুলো অদৃশ্য করে দেয়। সময় জটিলতা O(n)।