পাইথনে সমুদ্র দৃশ্যমান হতে পারে এমন বিল্ডিংগুলি খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে বিভিন্ন ভবনের উচ্চতার তালিকা আছে। উচ্চতার মান উচ্চতা সহ একটি বিল্ডিং সমুদ্র দেখতে পারে যখন তার ডানদিকের প্রতিটি বিল্ডিং সেই বিল্ডিংয়ের চেয়ে ছোট হয়। আমাদের বিল্ডিং সূচকগুলি খুঁজে বের করতে হবে যেখান থেকে আমরা আরোহী ক্রমে সমুদ্র দেখতে পাব।

সুতরাং, যদি ইনপুটটি উচ্চতার মত হয় =[8, 12, 12, 9, 10, 6], তাহলে আউটপুট হবে [2, 4, 5] কারণ আমরা সূচক 2-এ উচ্চতা 12 বিল্ডিং থেকে সমুদ্র দেখতে পাচ্ছি, থেকে সূচক 10 এ বিল্ডিং উচ্চতা 10 এবং সূচক 5 এ শেষ বিল্ডিং থেকে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• স্ট্যাক :=একটি নতুন তালিকা
• প্রতিটি সূচক আইডিএক্স এবং উচ্চতায় h উচ্চতার জন্য, করুন
  • যখন স্ট্যাক খালি না থাকে এবং উচ্চতা থাকে [স্ট্যাকের উপরে] <=h, do
    • স্ট্যাক থেকে শেষ উপাদান মুছুন
• স্ট্যাকের মধ্যে idx পুশ করুন
• রিটার্ন স্ট্যাক

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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

heights = [8, 12, 12, 9, 10, 6]
print(solve(heights))

ইনপুট

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

আউটপুট

[2, 4, 5]