剑指 判断栈
栈的压入、弹出序列
http://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106
模拟入栈出栈动作,遍历入栈数组,将数字都放入栈中,然后判断栈顶元素是否和pop数组的元素相当,如果相等的话,就pop出栈内元素,同时pop数组指针加1,当pop数组都遍历完,返回True 否则false。注意需要判断栈内是否为空。也就是当popv pushv 元素一直不相等时,pushv中的元素可以入栈,看是否后面有元素可以满足条件,当一旦一个元素与popV中元素满足,后面匹配的元素就只有两种选择,一个是当前元素出栈以后,一个是再下一个入栈的元素。
注意条件 当pushV popV pushV 和popV长度不相等。
class Solution: def IsPopOrder(self, pushV, popV): # write code here stack=[] i=0 for push_item in pushV: stack.append(push_item) while len(stack)!=0 and stack[-1]==popV[i]: stack.pop() i+=1 if i ==len(popV): return True if i<len(popV): return False
遍历pushV,当与popV中元素不相等的话,就放入栈中,便于后续弹出遍历,当相等的时候,pushV和popV的下标都加1,看下一个元素是否相同,如果这个时候栈不为空,看下栈顶元素是否与popV当前元素相同,如果相同popV下标加1,如果不相同看下当前pushV下标元素与当前popV元素是否相同,当pushV所有元素都遍历结束,可以看下栈中是否有元素如果有元素返回False,否则True。
class Solution: def IsPopOrder(self, pushV, popV): # write code here i=0 j=0 stack=[] if len(popV)==0 or len(pushV)==0 or len(popV)!=len(pushV): return False while j <len(pushV): if popV[i]!=pushV[j]: stack.append(pushV[j]) j+=1 else: #j+=1 i+=1 j+=1 while len(stack)!=0 and stack[-1]==popV[i]: i+=1 stack=stack[:-1] print(i) if len(stack)!=0: return False else: return True