题目分析

这个题目是我在面试时遇到的一个手撕代码题，题目意思非常简单，可以利用栈的思想，小伙伴们使用20分钟，看一看能否实现。

栈

这道题有如下三点说明：

在N层括号中，数据的个数就是数组的N维的维度。
如[[1, 2, 3], [4, 5, 6]]，在第一层括号中，有两个数据，分别是[1, 2, 3]和[4, 5, 6]，在第二层括号中有3个数据，为[1, 2, 3]，计算[4, 5, 6]也一样。判断层数时，根据右括号进行判断，栈中存在多少个左括号说明在多少层中。
给定的数组都是正确的，假设第k维的尺寸为K，计算k维所有数字是计算k - 1维所有数字的K倍，因为对于k - 1维的每一个数据，都时一个长度维K的数组。
如[[1, 2, 3], [4, 5, 6]]，第2维的所有数字为6，第1维的所有数字为3，说明第二维的长度为2。
可以通过检查逗号判断数据个数，遇到左括号或者逗号，可以将相应层数的数字加1。

对于上面这个例子，用一个图进行说明。

算法只需要遍历一次字符串即可，且只需要一个数组保存前k维的数据个数，因此**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

import sys


for line in sys.stdin:
    s = line.strip()
    stack = []
    res = []
    for c in s:
        if c == '[':
            stack.append('[')
            if len(res) < len(stack):
                res.append(1)
            else:
                res[len(stack) - 1] += 1
        elif c == ',':
            res[len(stack) - 1] += 1
        elif c == ']':
            stack.pop()
    for i in range(len(res) - 1, 0, -1):
        res[i] //= res[i - 1]
    print(res)

思维拓展

如果要判断数组是否合法，合法输出shape，不合法输出-1，则该如何求解呢？

其实只需要再加一个数组，每次遇到右括号，将当前维度的大小保存到数组中，下次再遇到相同维度的右括号时，进行比较，如果大小不一致，则返回-1即可。

用一个图进行说明，与上面那种算法思想类似，但是实现有所区别，小伙伴们可以比较一下两种算法。

算法也只需要遍历一次字符串即可，需要两个数组，temp保存当前第k维的数据个数，res保存之前第k维的数据个数，因此**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

import sys


for line in sys.stdin:
    s = line.strip()
    stack = []
    res = []
    temp = []
    for idx, c in enumerate(s):
        if c == '[':
            stack.append('[')
            if len(temp) < len(stack):
                temp.append(1)
                res.append(0)
            else:
                temp[len(stack) - 1] = 1
        elif c == ',':
            temp[len(stack) - 1] += 1
        elif c == ']':
            if not stack or s[idx - 1] == '[':
                res = -1
                break
            if not res[len(stack) - 1]:
                res[len(stack) - 1] = temp[len(stack) - 1]
            elif res[len(stack) - 1] != temp[len(stack) - 1]:
                res = -1
                break
            stack.pop()
    print(res) if not stack and s else print(-1)

刷题总结

两种栈的做法都可以解决这个问题，我更推荐第二种做法，不但提高了代码的鲁棒性而且思路非常好，符合人的思考方式，小伙伴们如何认为呢？