Đề bài
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.
Ràng buộc
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 1,000,000,000
Ví dụ
Đầu vào:
heights = [2, 1, 5, 6, 2, 3]
Kết quả mong đợi:
expected = 10Đầu vào:
std::vector<long long> heights = {2, 1, 5, 6, 2, 3};
Kết quả mong đợi:
long long expected = 10;Đầu vào:
long[] heights = new long[] {2, 1, 5, 6, 2, 3};
Kết quả mong đợi:
long expected = 10;Giải thích
Bars 5 and 6 together give a 2-wide rectangle of height 5: area 10.
Đầu vào:
heights = [4]
Kết quả mong đợi:
expected = 4Đầu vào:
std::vector<long long> heights = {4};
Kết quả mong đợi:
long long expected = 4;Đầu vào:
long[] heights = new long[] {4};
Kết quả mong đợi:
long expected = 4;Giải thích
A single bar of height 4 has area 4.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Hình chữ nhật tốt nhất cho một cột phụ thuộc vào nó có thể kéo dài bao xa trước khi gặp cột thấp hơn.
Gợi ý 2
Dùng stack tăng đơn điệu để tìm cột nhỏ hơn gần nhất ở cả hai phía cho từng cột.
Gợi ý 3
Đừng quên các cột không bị pop cho tới cuối, và xử lý nhất quán các chiều cao bằng nhau.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.