84. Largest Rectangle in Histogram

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

Table of Contents

1. Cách tiếp cận vấn đề

Đề bài cho 1 biểu đồ bao gồm nhiều cột, mỗi cột có chiều rộng cố định là 1 và có chiều cao khác nhau được định nghĩa trong mảng heights. Yêu cầu tìm ra diện tích của hình chữ nhật lớn nhật được tạo từ 1 hoặc nhiều cột trong biểu đồ đó.Ví dụ:

• Input: heights = [2,1,5,6,2,3]
• Output: 10

Trong hình trên, ta thấy 2 cột có chiều cao 5 và 6 tạo thành 1 hình chữ nhật có chiều rộng là 2 và chiều cao là 5, diện tích là 10 - cũng là diện tích lớn nhất.

Để tìm được diện tích lớn nhất thì ta phải tìm được tất cả diện tích còn lại đã, và tìm trong các diện tích đó cái nào là lớn nhất. Diện tích thì bằng chiều rộng x chiều cao, chiều cao thì cố định ở từng cột rồi, vậy ta cần phải tìm cách để mở rộng chiều rộng nhiều nhất có thể.

Thật vậy, khi nhìn vào từng cột, ta có thể thấy một số cột có thể được mở rộng về cả hai bên trái phải, một số cột chỉ mở rộng được một bên, và một số cột không thể mở rộng được, ví dụ đi từng cột theo thứ tự từ trái sang phải: 

1. Cột thứ nhất: Có chiều cao là 2 và không thể mở rộng sang bên phải, do cột bên phải có chiều cao thấp hơn nó 👉 Diện tích = 2 x 1 = 2
2. Cột thứ hai: Có chiều cao là 1 và có thể mở rộng chiều cao sang tất cả các cột khác vì nó là chiều cao nhỏ nhất 👉 Diện tích = 1 x 6 = 6
3. Cột thứ ba: Có chiều cao là 5 và chỉ có thể mở rộng sang cột thứ tư với chiều cao là 6, cột thứ năm có chiều cao thấp hơn là 2 nên không thể mở rộng sang phải, tương tự cột thứ hai có chiều cao cũng thấp hơn là 1 nên không thể mở rộng sang trái 👉 Diện tích = 5 x 2 = 10
4. Cột thứ tư: Có chiều cao là 6 và không thể mở rộng sang cả trái và phải, vì 6 hiện tại đang là chiều cao lớn nhất trong biểu đồ 👉 Diện tích = 6 x 1 = 6
5. Cột thứ năm: Có chiều cao là 2 và có thể mở rộng sang trái 2 cột và sang phải 1 cột 👉 Diện tích = 2 x 4 = 8
6. Cột thứ sáu: Có chiều cao là 3 và không thể mở rộng sang bên trái do cột thứ năm có chiều cao thấp hơn nó 👉 Diện tích = 3 x 1 = 3

Suy ra được, về ý tưởng chung để tìm được chiều rộng mà một cột tạm gọi là c có thể mở rộng ra, ta cần phải tìm được 2 giá trị sau:

• Vị trí của cột thấp hơn đầu tiên về phía bên trái của cột c: leftIdx
• Vị trí của cột thấp hơn đầu tiên về phía bên phải của cột c: rightIdx

-> Diện tích sẽ bằng: (rightIdx - leftIdx - 1) x Chiều cao cột c

Hoặc: rightIdex x Chiều cao cột c (Nếu không tìm thấy leftIdx)

Từ ý tưởng đó, ta có thể thấy cách làm đơn giản nhất là sử dụng BruteForce:

• 1 vòng lặp for duyệt qua từng cột (O(n))
• 1 vòng lặp để tìm vị trí nhỏ hơn đầu tiên bên trái (O(n))
• 1 vòng lặp để tìm vị trí nhỏ hơn đầu tiên bên phải (O(n))
• Từ đó tính toán diện tích và tìm max.
• Tuy nhiên như chúng ta đã biết thì cách làm này chưa phải là tối ưu nhất với time complexity là O(n) * (2O(n)) = 2O(n^2) = O(n^2) và ta cần tìm cách để khắc phục nó.

Để khắc phục thì ta phải hiểu vấn đề nằm ở đâu đã, và dễ thấy nó nằm ở ngay việc tìm vị trí nhỏ hơn đầu tiên ở 2 bên trái phải. Vậy làm sao để giảm độ phức tạp của nó từ O(n) xuống O(1)? Và từ đó cũng giảm được độ phức tạp chung của giải thuật từ O(n^2) xuống còn O(n)?

Chắc chắn ta cần một giải thuật tìm kiếm tối ưu hơn cộng thêm một cấu trúc dữ liệu phù hợp cho bài toán con:

Tìm vị trí nhỏ hơn đầu tiên bên trái và bên phải của từng cột. 

2. Solution & Phân Tích

Thay vì tư duy xuôi là duyệt qua từng cột và cố gắng đi tìm vị trí nhỏ hơn đầu tiên ở 2 bên thì ta có thể tư duy ngược lại là:

• Mỗi lần duyệt qua một cột ở vị trí i, ta sẽ coi i là vị trí nhỏ hơn đầu tiên bên phải và sẽ kiểm tra xem trước đó có bao nhiêu cột có chiều cao lớn hơn hoặc bằng nó và tính luôn diện tích của những cột đó.

Nhưng mà khoan đã, chẳng phải như vậy thì ta mới chỉ tìm được giá trị nhỏ hơn đầu tiên bên phải là i hay sao, còn giá trị nhỏ hơn đầu tiên bên trái thì sao? Vì để tính được diện tích thì ta cần phải có đủ 2 vị trí cơ mà.

Đơn giản là vì mỗi lần duyệt qua 1 cột, ta đã tính diện tích cho những cột lớn hơn hoặc bằng nó rồi nên những cột còn lại ở bên trái chưa được tính toán hiển nhiên là những cột có chiều cao thấp hơn, và cột chưa được tính toán diện tích đầu tiên bên trái chính là cột có chiều cao nhỏ hơn đầu tiên bên trái mà ta cần tìm.

 Để giải thích đơn giản thì các bạn có thể xem qua một vài ví dụ minh hoạ bên dưới:

Ta sẽ bắt đầu giải thuật bằng 1 vòng lặp for lặp qua tất cả các cột, với mỗi cột:

• Ở hình bên trái:
• Cột đầu tiên: do là cột đầu tiên nên ta chưa vội tính mà lưu nó vào đâu đó.
• Cột thứ hai: cột này có chiều cao cao hơn cột đầu tiên nên nó đang giúp cột đầu tiên mở rộng, ta sẽ không tính được diện tích ngay lúc này cho cả 2 cột đầu tiên và thứ hai.
• Cột thứ ba: ta tìm thấy cột thứ hai có chiều cao lớn hơn cột đang làm mốc, nên ta sẽ tính toán được diện tích cho cột thứ hai với chiều rộng = vị trí cột thứ ba - vị trí cột thứ nhất - 1.
• Sau cùng còn 2 cột đầu tiên và cuối cùng chưa được tính toán, 2 cột này tạo thành những cột với thứ tự tăng dần, chúng có chung vị trí nhỏ nhất đầu tiên bên phải là 1 cột ảo (cột thứ tư với chiều cao bằng 0 do tự tưởng tượng ra). Ta cần tìm giá trị nhỏ hơn đầu tiên bên trái của mỗi cột:
• Tính từ cột thứ hai trước, cột chưa được tính diện tích ở bên trái của nó là cột đầu tiên, nên vị trí nhỏ hơn đầu tiên bên trái của nó chính là cột đầu tiên luôn, diện tích được tính với chiều rộng = vị trí cột thứ tư - vị trí cột đầu tiên - 1.
• Chỉ còn lại cột đầu tiên, cột này không có cột nào bên trái nữa, diện tích được tính với chiều rộng = vị trí cột thứ tư.
• Tương tự với hình ở bên phải:
• Khi duyệt qua cột thứ ba, ta sẽ tính được diện tích cho 2 cột trước nó, vì cột thứ ba có chiều cao nhỏ nhất rồi.
• Cuối cùng ta sẽ duyệt qua cột ảo ở vị trí thứ tư để tính diện tích cho cột thứ ba đó.

Như vậy dựa vào tính chất của giải thuật này, thì cấu trúc dữ liệu Stack là hoàn toàn phù hợp, khi nó cho phép ta:

• Push vị trí index của những cột chưa tính toán được chiều cao vào stack
• Khi duyệt qua từng cột, ta có thể kiểm tra chiều cao của các cột chưa được tính toán diện tích trước đó thông qua method peek(), để xem cột đang duyệt hiện tại có phải là cột có vị trí nhỏ hơn đầu tiên bên phải của các cột chưa được tính toán đang nằm trong Stack hay không.
• Những cột nào có chiều cao lớn hơn hoặc bằng cột đang xét thì sẽ được pop() ra và tính toán diện tích, để đảm bảo những vị trí còn lại trong Stack luôn được duy trì theo thứ tự tăng dần.

Ta có thể xem qua các trường hợp hay gặp bên dưới, để thấy cụ thể hơn nó chính là Monotonic Stack - Stack duy trì các giá trị tăng dần hoặc giảm dần (Trong trường hợp này là tăng dần).

• Hình đầu tiên: Tại mỗi thời điểm duyệt qua từng cột, ta đều thấy Stack duy trì tăng dần, mãi tới khi duyệt tới cột ảo cuối cùng (với chiều cao bằng 0) thì ta mới có cơ hội để pop tất cả giá trị ra khỏi Stack.
• Hình thứ hai: Tại mỗi thời điểm, ta chỉ lưu được 1 cột, do khi duyệt qua từng cột nó sẽ pop ngay các cột ở trước đó ra và tính toán.
• Hình cuối cùng: Tương tự với hình thứ hai khi ta sẽ pop ra những cột có chiều cao lớn hơn hoặc bằng cột đang xét.
• Đối với tất cả các dạng khác bản chất cũng quy về các trường hợp trên mà thôi, vì khi xét 2 cột trước sau thì sẽ chỉ có 3 khả năng: cột sau lớn hơn, cột sau nhỏ hơn hoặc bằng nhau.

Time-Complexity: O(n). Mặc dù sử dụng vòng for để duyệt qua từng phần tử, mỗi phần tử tại dùng vòng lặp while để dò các phần tử lớn hơn hoặc bằng ở trước nó, tuy nhiên mỗi phần tử chỉ được push hoặc pop 1 lần duy nhất nên độ phức tạp của vòng while.

Space-Complexity: O(n) - Do sử dụng thêm bộ nhớ ngoài Stack

Với n là số lượng các phần tử trong mảng input heights.

3. Code

Ở vòng for đầu tiên, ta sẽ duyệt qua tất cả các cột, với mỗi cột ta sẽ:

• Dùng vòng lặp while để kiểm tra trong stack xem có bao nhiêu cột chưa được tính diện tích mà có chiều cao lớn hơn hoặc bằng chiều cao đang xét
• Nếu có tồn tại cột như vậy thì tiến hành pop ra index từ stack để tính diện tích với:
• Chiều cao: giá trị trong mảng heights
• Chiều rộng:
• Nếu trong stack không còn lại giá trị nào (không thể có giá trị nhỏ hơn đầu tiên bên trái) thì chiều rộng bằng index của cột đang xét
• Ngược lại thì vị trí của cột nhỏ hơn đầu tiên bên trái chính là index của cột tiếp theo trong stack và chiều rộng = index của cột đang xét - index cột tiếp theo trong stack - 1.
• Nếu không tồn tại thì chứng tỏ cột đang xét lớn hơn tất cả các cột hiện tại trong Stack, tiến hành push vị trí của cột đang xét vào Stack để xếp hàng chờ đến lượt được tính diện tích.

Sau cùng khi duyệt qua tất cả các cột, mà vẫn không tìm thấy được cột nhỏ hơn đầu tiên bên phải nào để tính diện tích cho các cột trong Stack, ta sẽ ngầm hiểu vẫn còn 1 cột ảo ở vị trí len với chiều cao nhỏ nhất bằng 0 được dùng để cố định và tính diện tích cho tất cả các cột còn lại trong Stack. Đó là lý do tại sao có thêm 1 vòng lặp while nữa áp dụng logic tương tự nêu ở trên với index được xét có giá trị bằng len - chiều dài của mảng heights.

© hieulm2k | Buy me a coffee