JZX轻语：简

LeetCode 1441 - 用栈操作构建数组

发表于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

题目链接：https://leetcode.cn/problems/build-an-array-with-stack-operations/