สมมติว่าเรามีจำนวนอาร์เรย์ที่มีลูกบาศก์ที่แตกต่างกัน n ก้อน พวกมันจะถูกวางในแนวนอน เราต้องสร้างกองลูกบาศก์ในแนวตั้ง คิวบ์ใหม่ควรเป็นไปตาม −
- ถ้าคิวบ์ ith อยู่บนคิวบ์ที่ j ความยาวด้านของ jth จะต้องมากกว่าหรือเท่ากับความยาวด้านของ ith หนึ่ง
เมื่อเราทำเสาเข็มแนวตั้ง เราสามารถนำลูกบาศก์จากด้านซ้ายหรือด้านขวาเท่านั้น แต่ไม่เอาจากตรงกลาง เราต้องเช็คก่อนว่าจะซ้อนได้หรือไม่
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1,2,3,7,8] ผลลัพธ์จะเป็น True เพราะเราสามารถนำกล่องจากขวาไปซ้ายเพื่อรวมเข้าด้วยกันได้สำเร็จ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ nums
- d :=สร้างคิวสองสิ้นสุดจากองค์ประกอบของ nums
- flag :=จริง
- ก่อนหน้า :=0
- ในขณะที่ d ไม่ว่างเปล่า ทำ
- ก่อน :=d[0]
- สุดท้าย :=d[n-1]
- หาก prev ไม่เหมือนกับ 0 และ (first> prev หรือ last> prev) แล้ว
- ธง :=เท็จ
- ออกมาจากวงจร
- ถ้าก่อน>=สุดท้ายแล้ว
- prev :=เหลือรายการ d และลบออกจาก d
- มิฉะนั้น
- prev :=รายการสุดท้ายของ d และลบออกจาก d
- ถ้าแฟล็กเป็นจริง
- คืนค่า True
- มิฉะนั้น
- คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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
