11. Container With Most Water

Đề bài

Cho mảng height gồm n số nguyên không âm. Mỗi phần tử height[i] biểu diễn một đường thẳng đứng tại hoành độ i, có chiều cao height[i] (điểm đầu ở $(i, height[i])$ và điểm cuối ở $(i, 0)$).

Hãy chọn hai đường thẳng sao cho cùng với trục x tạo thành một “thùng chứa” được nhiều nước nhất. Trả về diện tích nước tối đa (diện tích hình chữ nhật bị giới hạn bởi hai đường thẳng và trục x).

Lưu ý:

• Bạn không được nghiêng thùng chứa.
• n >= 2.

Với height = [1,8,6,2,5,4,8,3,7] thì diện tích lớn nhất là 49.

Ví dụ 1:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Tóm tắt đề

Chọn 2 chỉ số i < j:

• Chiều rộng: $j - i$
• Chiều cao: $\min(height[i], height[j])$
• Diện tích: $(j - i) * \min(height[i], height[j])$

Hãy tìm diện tích lớn nhất có thể.

Ý tưởng

Dùng 2 con trỏ đối đầu:

• Đặt start = 0, end = n-1.
• Mỗi bước tính diện tích với cặp hiện tại, cập nhật đáp án lớn nhất.
• Sau đó dịch con trỏ ở phía có chiều cao nhỏ hơn, vì:
  • Diện tích bị giới hạn bởi chiều cao nhỏ hơn.
  • Nếu giữ chiều cao nhỏ hơn và thu hẹp khoảng cách thì diện tích không thể tăng; muốn tăng phải hy vọng gặp được cột cao hơn ở phía đó.

Code

package leetcode

func maxArea(height []int) int {
	max, start, end := 0, 0, len(height)-1
	for start < end {
		width := end - start
		high := 0
		if height[start] < height[end] {
			high = height[start]
			start++
		} else {
			high = height[end]
			end--
		}

		temp := width * high
		if temp > max {
			max = temp
		}
	}
	return max
}

---