Giả sử chúng ta có một dãy nums chứa kích thước của n hình khối khác nhau, chúng được đặt theo chiều ngang. Chúng ta phải tạo một đống hình khối theo chiều dọc. Khối lập phương mới sẽ theo sau -
- nếu hình lập phương thứ i nằm trên hình lập phương thứ j, thì chiều dài cạnh của hình lập phương thứ j phải lớn hơn hoặc bằng chiều dài cạnh của hình lập phương thứ i.
Khi chúng tôi làm đống dọc, chúng tôi chỉ có thể lấy các hình khối từ phía bên trái hoặc bên phải chứ không thể lấy từ giữa. Chúng tôi phải kiểm tra xem chúng tôi có thể xếp chồng lên nhau hay không.
Vì vậy, nếu đầu vào giống như nums =[1,2,3,7,8], thì đầu ra sẽ là Đúng vì chúng ta có thể lấy các hộp từ phải sang trái để chồng chúng thành công.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của nums
- d:=tạo một hàng đợi kết thúc kép từ các phần tử của nums
- cờ:=True
- trước:=0
- trong khi d không trống, hãy thực hiện
- đầu tiên:=d [0]
- cuối cùng:=d [n-1]
- nếu trước đó không giống 0 và (đầu tiên> trước hoặc cuối cùng> trước), thì
- cờ:=Sai
- ra khỏi vòng lặp
- if đầu tiên> =last, then
- prev:=mục bên trái của d và xóa mục đó khỏi d
- nếu không,
- before:=mục cuối cùng của d và xóa nó khỏi d
- nếu cờ là true, thì
- trả về True
- nếu không,
- trả về Sai
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
from collections import deque
def solve(nums):
n = len(nums)
d = deque(nums)
flag = True
prev = 0
while d:
first = d[0]
last = d[-1]
if prev != 0 and (first > prev or last > prev):
flag = False
break
if first >= last:
prev = d.popleft()
else:
prev = d.pop()
if flag:
return True
else:
return False
nums = [1,2,3,7,8]
print(solve(nums)) Đầu vào
[1,2,3,7,8]
Đầu ra
True