ยาก 1 ข้อที่แก้แล้ว อัตราผ่าน 100.0%

Largest Rectangle in a Histogram

Find the largest rectangle that fits under a histogram.

สิ่งที่คุณจะได้เรียนรู้

  • Find each bar's widest rectangle
  • Use a stack of increasing heights
  • Solve the problem in linear time

โจทย์

ดูฉบับแปล

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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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.

ตัวอย่างที่ 2
อินพุต:
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

The best rectangle for a bar depends on how far it can extend before a shorter bar blocks it.

คำใบ้ 2

Use a monotonic increasing stack to find each bar’s nearest smaller bar on both sides.

คำใบ้ 3

Don’t forget bars that never get popped until the end, and handle equal heights consistently.

ความซับซ้อนที่คาดหวัง

O(n) time, O(n) extra space

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

# นักโค้ด ภาษา เวลา หน่วยความจำ คะแนนจาก AI คำตอบ
1 ННикита Python 996 ms - 5/5 ดูโค้ด

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

สปอยล์: มีคำตอบเต็ม 1 ข้อด้านล่าง ลองแก้ด้วยตัวเองก่อน คุณยังสามารถดูโค้ดของนักพัฒนาคนอื่นและรีวิว AI ได้ เข้าสู่ระบบและแก้โจทย์เพื่อร่วมพูดคุย