मान लीजिए हमारे पास विभिन्न इमारतों की ऊंचाइयों की एक सूची है। ऊंचाई मान heights[i] वाली इमारत समुद्र देख सकती है जब उसके दाईं ओर की हर इमारत उस इमारत से छोटी हो। हमें उन इमारतों के इंडेक्स ढूंढने हैं जहां से हम समुद्र देख सकते हैं, आरोही क्रम में।
इसलिए, यदि इनपुट है heights = [8, 12, 12, 9, 10, 6], तो आउटपुट होगा [2, 4, 5] क्योंकि हम इंडेक्स 2 पर ऊंचाई 12 वाली इमारत से, इंडेक्स 4 पर ऊंचाई 10 वाली इमारत से और अंतिम इमारत इंडेक्स 5 से समुद्र देख सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
stack :=एक नई सूचीheightsमें प्रत्येक इंडेक्सidxऔर ऊंचाईhके लिए, करें:- जब
stackखाली नहीं है औरheights[stack के शीर्ष] <= h, करें:stackसे अंतिम तत्व हटाएं
- जब
idxकोstackमें डालेंstackलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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]