递归法 | #栈的压入、弹出序列#
栈的压入、弹出序列
https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
python3, 递归法。
初始情况:
- 都空,True。
- 长度不同;长度同,但元素对应不上。都返回False。(题目保证了pushV 的所有数字均不相同,这里用set(list)可以做判断)
- 长度<=2, 一定能对应压入和弹出,返回True。
递归关键:
popV的第一个点是最先pop的,第二个点是其次pop的。反映在pushV中, 第二个点 一定在第一个点的 后面 或者 前一位 ,否则返回False。(这里先判断一下,是否在pushV的首位,因为首位没有前一位)
上一步不返回False,则说明第一个点是暂时合格的,然后pushV和popV都弹出该点(脑中模拟一下栈弹出的过程),再继续递归。
class Solution: def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool: def IsPalindrome(pu, po): if len(pu) <= 2: return True a = pu.index(po[0]) if a == 0: return IsPalindrome(pu[1:], po[1:]) if po[1] not in pu[a-1:]: return False pu.pop(a) po.pop(0) return IsPalindrome(pu, po) if not pushV and not popV: return True if len(pushV) != len(popV) or set(pushV) != set(popV): return False if len(pushV) <= 2: return True return IsPalindrome(pushV, popV)