Chương trình Python kiểm tra có thể xếp chồng khối lập phương không

Cho mảng nums kích thước các khối lập phương đặt ngang. Muốn xếp chồng dọc sao cho khối trên luôn có cạnh ≤ khối dưới. Chỉ được lấy khối từ hai đầu (trái hoặc phải). Kiểm tra xem có thể xếp hết tất cả khối không.

Ví dụ: [1,2,3,7,8] → True (lấy từ phải sang trái: 8,7,3,2,1).

Thuật toán tham lam (Greedy) với Deque

• Dùng deque để lấy đầu/cuối O(1).
• Biến prev lưu cạnh khối vừa đặt (khối dưới).
• Mỗi bước: chọn khối lớn hơn ở hai đầu (miễn là ≤ prev).
• Nếu cả hai đầu đều > prev → thất bại.

Ví dụ mã nguồn

from collections import deque

def solve(nums):
    d = deque(nums)
    prev = 0
    while d:
        first, last = d[0], d[-1]
        if prev != 0 and (first > prev or last > prev):
            return False
        if first >= last:
            prev = d.popleft()
        else:
            prev = d.pop()
    return True

nums = [1,2,3,7,8]
print(solve(nums))  # True

Đầu vào / Đầu ra

Input:  [1,2,3,7,8]
Output: True