สมมติว่าเรามีอาเรย์ nums ที่เก็บขนาดของ n ลูกบาศก์ต่างกัน วางในแนวนอน เราต้องทำกองลูกบาศก์ในแนวตั้ง ลูกบาศก์ใหม่ต้องปฏิบัติตามกฎ: หากลูกบาศก์ที่ i อยู่บนลูกบาศก์ที่ j ด้านข้างของ j ต้องมากกว่าหรือเท่ากับด้านข้างของ i
เมื่อทำกองแนวตั้ง เราสามารถหยิบลูกบาศก์ได้เฉพาะจากด้านซ้ายหรือขวาเท่านั้น ไม่ได้จากกลาง เราต้องตรวจสอบว่าสามารถซ้อนได้หรือไม่
ตัวอย่างเช่น หาก nums = [1,2,3,7,8] ผลลัพธ์จะเป็น True เพราะเราสามารถหยิบจากขวาไปซ้ายเพื่อซ้อนได้สำเร็จ
ขั้นตอนการแก้ปัญหา
- n := ขนาดของ nums
- d := สร้าง double-ended queue (deque) จากสมาชิกของ nums
- flag := True
- prev := 0
- while d ไม่ว่าง:
- first := d[0], last := d[-1]
- ถ้า prev != 0 และ (first > prev หรือ last > prev): flag := False, ออกจากลูป
- ถ้า first >= last: prev := d.popleft()
- มิฉะนั้น: prev := d.pop()
- ถ้า flag เป็น True: คืนค่า True มิฉะนั้นคืนค่า False
ตัวอย่างโค้ด
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))
อินพุต
[1,2,3,7,8]
เอาต์พุต
True
