Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/container-with-most-water/description/
Table of Contents
1. Cách tiếp cận vấn đề
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: Dựa vào hình trên ta có thể thấy mỗi giá trị tại mảng height đại diện cho chiều cao của các cạnh, ta cần tìm ra diện tích bể chứa được tạo bởi 2 cạnh sao cho diện tích đó là lớn nhất, trong trường hợp này thì diện tích đó là 49
Để diện tích của bể chứa là lớn nhất thì chắc chắn 2 cạnh của bể phải nằm cách xa nhau nhất có thể, và công thức để tính diện tích của cặp cạnh bất kỳ là:
S = min(chiều cao cạnh left, chiều cao cạnh right) x (vị trí cạnh right - vị trí cạnh 1eft)
Chính vì lý do đó ta sẽ sử dụng kỹ thuật 2 Pointers để giải bài toán này, với 1 left pointer nằm ở vị trí index 0 tăng đến khi nào gặp right và 1 right pointer nằm ở vị trí index n - 1 giảm đến khi nào gặp left. (với n là số lượng các cạnh trong mảng)
2. Solution & Phân Tích
Tuy nhiên với kỹ thuật 2 Pointers thì 1 điều quan trọng ta cần xác định là khi nào ta cần tăng con trỏ left và khi nào ta cần giảm con trỏ right? Mục đích của việc tăng giảm này là để tìm ra được cặp cạnh mới có diện tích là lớn nhất, tuy nhiên mỗi lần tăng giảm thì (vị trí cạnh right - vị trí cạnh 1eft) sẽ giảm lại nên để tăng diện tích ta bắt buộc phải tìm kiếm 1 cạnh mới với chiều cao lớn hơn hay min(chiều cao cạnh left, chiều cao cạnh right) phải cho ra được giá trị lớn hơn, sẽ có 2 trường hợp xảy ra:
- Nếu chiều cao cạnh left hiện tại đang nhỏ hơn cạnh right: Ta cần phải lưu lại current value tại left và tăng left cho đến khi nào tìm được cạnh có chiều cao cao hơn current value đã lưu, nếu không thì diện tích sẽ không tăng lên được.
- Nếu chiều cao cạnh right hiện tại đang nhỏ hơn cạnh left: Với cùng lý do tương tự, ta cần phải giảm right cho đến khi nào tìm được cạnh có chiều cao cao hơn current value đã lưu cho right.
Time-Complexity: O(n)
Space-Complexity: O(1)
Với n là số lượng các phần tử trong mảng input.