समस्या
A histogram has bars of width 1 with the given heights. Find the area of the largest rectangle that lies entirely within the bars. A monotonic stack gives an O(n) solution.
Implement largest_rectangle(heights).
Input
heights: Bar heights from left to right.
Output
Return the largest area.
सीमाएँ
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 1,000,000,000
उदाहरण
इनपुट:
heights = [2, 1, 5, 6, 2, 3]
अपेक्षित आउटपुट:
expected = 10इनपुट:
std::vector<long long> heights = {2, 1, 5, 6, 2, 3};
अपेक्षित आउटपुट:
long long expected = 10;इनपुट:
long[] heights = new long[] {2, 1, 5, 6, 2, 3};
अपेक्षित आउटपुट:
long expected = 10;व्याख्या
Bars 5 and 6 together give a 2-wide rectangle of height 5: area 10.
इनपुट:
heights = [4]
अपेक्षित आउटपुट:
expected = 4इनपुट:
std::vector<long long> heights = {4};
अपेक्षित आउटपुट:
long long expected = 4;इनपुट:
long[] heights = new long[] {4};
अपेक्षित आउटपुट:
long expected = 4;व्याख्या
A single bar of height 4 has area 4.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
किसी bar के लिए best rectangle इस बात पर निर्भर करता है कि वह कितनी दूर तक फैल सकता है, इससे पहले कि कोई shorter bar रोक दे.
संकेत 2
Monotonic increasing stack का use करके हर bar के दोनों sides पर nearest smaller bar खोजें.
संकेत 3
जो bars end तक pop नहीं होते उन्हें न भूलें, और equal heights को consistently handle करें.
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।