समस्या
Bars of width 1 have the given heights. After rain, water collects above each bar up to the lower of the tallest bars on its left and right. Compute the total trapped water. An O(n) two-pointer solution is expected.
Implement trapped_water(heights).
Input
heights: Bar heights from left to right.
Output
Return the total units of water.
सीमाएँ
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
उदाहरण
इनपुट:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
अपेक्षित आउटपुट:
expected = 6इनपुट:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
अपेक्षित आउटपुट:
long long expected = 6;इनपुट:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
अपेक्षित आउटपुट:
long expected = 6;व्याख्या
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
इनपुट:
heights = [3, 2, 1]
अपेक्षित आउटपुट:
expected = 0इनपुट:
std::vector<long long> heights = {3, 2, 1};
अपेक्षित आउटपुट:
long long expected = 0;इनपुट:
long[] heights = new long[] {3, 2, 1};
अपेक्षित आउटपुट:
long expected = 0;व्याख्या
Heights only go down, so water runs off: 0.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर position पर water level, left और right से दिखने वाली shorter tallest bar से सीमित होता है.
संकेत 2
दोनों ends से boundaries track करें, और हमेशा उस side को advance करें जिसकी current boundary छोटी हो.
संकेत 3
Empty input और equal-height plateaus का ध्यान रखें; वहाँ trapped water को सिर्फ smaller side ही determine कर सकती है.
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।