Elearning CodePath – CTP Online Judge

HÌNH CHỮ NHẬT LỚN NHẤT

ST_LargestRectangle

🟢 Hard #Stack

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một biểu đồ hình cột gồm $N$ cột xếp liền kề nhau, mỗi cột có chiều rộng bằng 1 đơn vị. Cột thứ $i$ có chiều cao là $h_i$.

Yêu cầu: Hãy tìm diện tích của hình chữ nhật có diện tích lớn nhất nằm bên trong biểu đồ hình cột đã cho.

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file ST_LargestRectangle.INP gồm:
- [cite_start]Dòng 1: Chứa số nguyên dương $N$ ($1 \le N \le 10^5$). [cite: 66]
- [cite_start]Dòng 2: Chứa $N$ số nguyên dương $h_1, h_2, \dots, h_n$ ($0 \le h_i \le 10^4$). [cite: 67]

### 📤 Định dạng Đầu ra

Ghi ra file ST_LargestRectangle.OUT một số nguyên duy nhất là diện tích hình chữ nhật lớn nhất tìm được.

### ✨ Ví dụ

| Input (ST_LargestRectangle.INP) | Output (ST_LargestRectangle.OUT) |
| :--- | :--- |
| 6 <br> 2 1 5 6 2 3 | 10 |

**Giải thích:**
Hình chữ nhật lớn nhất được tạo bởi hai cột có chiều cao 5 và 6. Chiều cao của hình chữ nhật này là $\min(5, 6) = 5$, chiều rộng là 2. Diện tích là $5 \times 2 = 10$.

### 🏷 Subtasks

- [cite_start]Subtask 1 (30%): $N \le 1000$. [cite: 73]
- [cite_start]Subtask 2 (70%): $N \le 10^5$. [cite: 73]

✅ Đã AC: 0 / 4 submissions