キューブを積み上げることができるかどうかをチェックするPythonプログラム

n個の異なる立方体のサイズを含む配列numがあるとすると、それらは水平に配置されます。立方体の山を垂直に作らなければなりません。新しいキューブは次のようになります-

• i番目の立方体がj番目の立方体の上にある場合、j番目の立方体の辺の長さはi番目の立方体の辺の長さ以上である必要があります。

縦パイルを作るときは、左側または右側からしか立方体をとることができず、中央からはとることができません。積み上げることができるかどうかを確認する必要があります。

したがって、入力がnums =[1,2,3,7,8]のような場合、ボックスを右から左に移動して正常に積み上げることができるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• n：=numsのサイズ
• d：=numsの要素から両端キューを作成します
• フラグ：=True
• prev：=0
• dが空でない場合は、
  • 最初：=d [0]
  • 最後：=d [n-1]
  • prevが0および（first>prevまたはlast>prev）と同じでない場合、
    • フラグ：=False
    • ループから抜け出す
  • 最初の場合>=最後の場合、
    • prev：=dのアイテムを残し、dから削除します
  • それ以外の場合、
    • prev：=dの最後のアイテムで、dから削除します
• フラグが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