发表于 2024.08.22

• 根据栈后进先出的特点，不难得知栈内的元素必定为递增序列，且对于栈中两个相邻的元素a和b，如果b - a > 1，那么a和b之间的元素（已经被弹出了）必定是在bPush前，发生了b - a - 1次Push和Pop操作（即这些中间的元素进栈后又出栈了，然后b入栈前，栈顶元素为a）。因此，我们可以使用prev记录上一个元素(初始值可为0)，然后遍历target数组，对于每个元素num，如果num - prev > 1，那么我们就需要num - prev - 1次Push和Pop操作，然后再通过一个Push将num压入栈内。最后返回所有操作的序列即可。

  class Solution:
      def buildArray(self, target: List[int], n: int) -> List[str]:
          prev = 0
          ans = []
          for num in target:
              mid_cnt = num - prev - 1  # 两个相邻元素之间有多少个中间元素
              # 此时这些中间元素已经不在栈里了，这意味着发生了Push和Pop
              for i in range(mid_cnt):  
                  ans.append("Push")
                  ans.append("Pop")
              ans.append("Push")
              prev = num
          return ans

• LC 题目链接