Largest Rectangle in Histogram

Q: Độ phức tạp thời gian của bài toán hình chữ nhật lớn nhất trong biểu đồ là bao nhiêu?

Lời giải dùng ngăn xếp đơn điệu chạy trong thời gian O(n) và cần thêm O(n) bộ nhớ: mỗi chỉ số được đưa vào ngăn xếp một lần và lấy ra một lần. Thử từng nhóm thanh cần thời gian O(n²) .

KhóNgăn xếp đơn điệu

+10

Biểu đồ tần suất là một hàng gồm các cột đứng cạnh nhau, không có khoảng trống, mỗi cột rộng một đơn vị: heights[i] là chiều cao của cột i. Một hình chữ nhật bên trong biểu đồ phủ một dãy các cột liền kề và không thể cao hơn cột thấp nhất trong dãy đó.

Trả về diện tích lớn nhất mà một hình chữ nhật như vậy có thể có.

Hàm

largestRectangleArea(heights: integer-array) → integer

heightsinteger-array: chiều cao của mỗi thanh, từ trái sang phải
Trả vềinteger: diện tích của hình chữ nhật lớn nhất có thể nằm gọn trong biểu đồ histogram

Ràng buộc

1 ≤ heights.length ≤ 2 × 10⁴
0 ≤ heights[i] ≤ 10⁵
Mỗi thanh rộng một đơn vị, vì vậy hình chữ nhật phủ từ thanh i đến j rộng j-i+1 đơn vị.

Ví dụ

Đầu vào: heights = [2, 5, 6, 3, 4, 1]
Đầu ra: 12
Giải thích: Các thanh 5, 6, 3 và 4 đều cao ít nhất 3, nên một hình chữ nhật cao 3 trải dài qua các thanh đó: 3 × 4 = 12. Hai thanh cao nhất chỉ cho ta 5 × 2 = 10.

Câu hỏi mở rộng

Giả sử mỗi thanh có độ rộng riêng, được cho trong một mảng thứ hai. Cần thay đổi gì trong lời giải dùng ngăn xếp một lượt?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Thử mọi đoạn thanh sẽ tốn khoảng n²/2 bước. Hãy nhìn theo cách khác: hình chữ nhật lớn nhất có chiều cao đúng bằng chiều cao của một thanh, nên mỗi thanh chỉ cần biết nó có thể trải rộng đến đâu trước khi gặp một thanh thấp hơn chặn lại. Ngăn xếp đơn điệu tìm ra các vị trí đó trong O(n).

Thử mỗi lần chạy với giá trị nhỏ nhất đang có

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Cố định start, tăng end từng thanh một và giữ lại chiều cao thấp nhất đã thấy. Hình chữ nhật tốt nhất trên đoạn đó có diện tích lowest × (end-start+1). Bắt đầu từ số 5 trong [2, 5, 6, 3, 4, 1], các đoạn lần lượt cho kết quả 5, 10, 9, 12 và 5.

Cách này chính xác vì mỗi hình chữ nhật nằm trên một đoạn nào đó và không thể cao hơn thanh thấp nhất của đoạn đó. Cách này chậm vì có n(n+1)/2 đoạn: khoảng 2 × 10^8 đoạn với 2 × 10^4 thanh.

Thuật toán

Đặt best thành 0.
Với mỗi start, đặt lowest thành heights[start].
Với mỗi end từ start đến thanh cuối cùng, đặt lowest thành heights[end] nếu thanh đó thấp hơn.
Cập nhật best bằng lowest × (end-start+1).
Trả về best.

def largestRectangleArea(heights):
    n = len(heights)
    best = 0
    for start in range(n):
        lowest = heights[start]
        for end in range(start, n):
            # The rectangle over start..end is as tall as the lowest bar in it.
            lowest = min(lowest, heights[end])
            best = max(best, lowest * (end - start + 1))
    return best

Thanh ngắn hơn gần nhất ở mỗi bên

Ý tưởng

Hình chữ nhật lớn nhất chạm đến đỉnh của ít nhất một thanh bên dưới nó; nếu không, bạn có thể nâng nó lên. Vì vậy, với mỗi thanh i, hãy lấy hình chữ nhật cao đúng heights[i] và kéo dài đến thanh thấp hơn gần nhất ở mỗi bên, tại left[i] và right[i] (lần lượt là -1 và n nếu không có thanh nào). Chiều rộng của hình chữ nhật là right[i]-left[i]-1.

Để tìm left[i], duyệt từ trái sang phải với một ngăn xếp các chỉ số có chiều cao tăng dần. Thanh i lấy ra khỏi ngăn xếp mọi thanh cao ít nhất bằng nó: không thanh nào trong số đó có thể là thanh thấp hơn gần nhất đối với i hoặc bất kỳ thanh nào ở phía sau, vì i gần hơn và không cao hơn. Khi đó, phần tử trên cùng là left[i]. Một lượt duyệt từ phải sang trái sẽ cho kết quả right[i].

Mỗi chỉ số được đẩy vào và lấy ra khỏi ngăn xếp nhiều nhất một lần trong mỗi lượt duyệt, nên độ phức tạp thời gian là O(n).

Thuật toán

Duyệt từ trái sang phải bằng một ngăn xếp. Với mỗi i, lấy phần tử ra khỏi ngăn xếp khi thanh trên cùng cao ít nhất bằng heights[i]; gán left[i] bằng phần tử trên cùng, hoặc bằng -1 nếu ngăn xếp rỗng; sau đó thêm i vào ngăn xếp.
Duyệt từ phải sang trái theo cách tương tự để tìm right[i], dùng n khi ngăn xếp rỗng.
Trả về giá trị lớn nhất của heights[i] × (right[i]-left[i]-1).

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n  # index of the nearest shorter bar on the left, or -1
    right = [n] * n  # index of the nearest shorter bar on the right, or n
    stack = []  # indices whose heights rise strictly from bottom to top
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    best = 0
    for i in range(n):
        # Bar i is the lowest bar of everything strictly between left[i] and right[i].
        best = max(best, heights[i] * (right[i] - left[i] - 1))
    return best

Một lượt duyệt với ngăn xếp đơn điệu

Ý tưởng

Lượt duyệt từ trái sang phải đã gặp mọi ranh giới bên phải rồi bỏ chúng đi. Khi cột i đẩy cột t ra khỏi ngăn xếp, cột i không cao hơn cột t, nên hình chữ nhật của t kết thúc tại đó. Ở bên trái, nó kết thúc tại below, chỉ số nằm ngay dưới t trên ngăn xếp, hoặc là -1 nếu ngăn xếp rỗng. Tính diện tích khi lấy ra khỏi ngăn xếp: heights[t] × (i - below - 1).

Đầu trái đó chính xác vì mọi cột nằm giữa một phần tử và phần tử ngay dưới nó đều bị phần tử đó đẩy ra khỏi ngăn xếp, trực tiếp hoặc qua một chuỗi liên tiếp, nên không cột nào thấp hơn phần tử đó. Một cột kết thúc có chiều cao 0 sẽ đẩy các cột còn lại ra khỏi ngăn xếp. Trong ví dụ đầu tiên, cột cao 1 ở chỉ số 5 đẩy cột cao 3 ở chỉ số 3 ra khỏi ngăn xếp, với chỉ số 0 ngay bên dưới: 3 × 4 = 12.

Đẩy một cột có chiều cao bằng nhau ra khỏi ngăn xếp sớm vẫn an toàn: cột xuất hiện sau sẽ kế thừa ranh giới bên trái của nó và tính diện tích cho toàn bộ đoạn liên tiếp.

Thuật toán

Bắt đầu với một ngăn xếp rỗng và best = 0.
Với i từ 0 đến n, lấy chiều cao heights[i], hoặc 0 khi i = n.
Trong khi thanh trên cùng cao ít nhất bằng chiều cao đó, lấy thanh ra và gán cho t, rồi cập nhật best bằng heights[t] × (i - below - 1), trong đó below là thanh trên cùng mới hoặc -1.
Đẩy i vào ngăn xếp.
Trả về best.

def largestRectangleArea(heights):
    n = len(heights)
    stack = []  # indices whose heights rise strictly from bottom to top
    best = 0
    for i in range(n + 1):
        current = heights[i] if i < n else 0  # a bar of 0 past the end empties the stack
        while stack and heights[stack[-1]] >= current:
            # Bar i stops the popped bar on the right; the bar below it stops it on the left.
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

Lỗi thường gặp và trường hợp biên

Quên các thanh vẫn còn trong ngăn xếp (stack). Với [1, 2, 3, 4, 5], không có thanh nào bị lấy ra trong vòng lặp (loop); nếu không có số 0 ở cuối, bạn sẽ trả về 0 thay vì 9.
Tính chiều rộng từ chỉ số của chính thanh vừa lấy ra. Trong ví dụ đầu tiên, thanh 3 ở chỉ số 3 trải dài từ chỉ số 1 đến 4; i - t cho kết quả 2 thay vì 4.
Tính chiều rộng sai khi ngăn xếp trống sau khi lấy một thanh ra. Chiều rộng là i: với [2, 1, 2], thanh 1 trải dài qua cả ba thanh, tạo ra diện tích là 3.
Chỉ lấy thanh ra khi gặp > trong phiên bản hai lượt. Với [3, 3, 3, 3], mỗi thanh khi đó chỉ có chiều rộng là 1, và bạn sẽ trả về 3 thay vì 12.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán hình chữ nhật lớn nhất trong biểu đồ là bao nhiêu?

Lời giải dùng ngăn xếp đơn điệu chạy trong thời gian O(n) và cần thêm O(n) bộ nhớ: mỗi chỉ số được đưa vào ngăn xếp một lần và lấy ra một lần. Thử từng nhóm thanh cần thời gian O(n²).

Có thể giải bài toán Hình chữ nhật lớn nhất trong biểu đồ bằng phương pháp chia để trị không?

Có. Thanh thấp nhất trong một phạm vi hoặc nằm dưới hình chữ nhật tốt nhất, khi đó diện tích là lowest × width, hoặc chia phạm vi thành hai phần để bạn giải riêng. Tìm giá trị nhỏ nhất khiến thuật toán này có độ phức tạp O(n log n) với đầu vào ngẫu nhiên và O(n²) với đầu vào đã sắp xếp; cây phân đoạn giúp thuật toán luôn có độ phức tạp O(n log n).

Cách dùng Largest Rectangle in Histogram để tìm hình chữ nhật lớn nhất trong lưới 0/1?

Duyệt từng hàng và đếm số lượng số 1 được xếp chồng lên nhau trong từng cột, tính đến hàng hiện tại; gặp số 0 thì đặt lại bộ đếm. Các số đếm của mỗi hàng tạo thành một biểu đồ cột, và hình chữ nhật lớn nhất của hàng đó là hình chữ nhật lớn nhất gồm các số 1 kết thúc ở hàng đó: tổng thời gian là O(rows × cols).

def largestRectangleArea(heights):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

heights = [2, 5, 6, 3, 4, 1]

Đầu ra mong đợi

Largest Rectangle in Histogram

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử mỗi lần chạy với giá trị nhỏ nhất đang có

Thanh ngắn hơn gần nhất ở mỗi bên

Một lượt duyệt với ngăn xếp đơn điệu

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự