本文共 17579 字，大约阅读时间需要 58 分钟。

来看下Leetcode中Tag为的题目

• [Leetcode 739] ：求下一个温暖天气距离当前日期的时间差。Medium

class Solution(object):    def dailyTemperatures(self, temperatures):        """        :type temperatures: List[int]        :rtype: List[int]        """        size,stack = len(temperatures),[]        ret = [0]*size        for idx,tem in enumerate(temperatures):            while(stack and temperatures[stack[-1]]

• [Leetcode 496] ：给定两个数组（无重复）nums1 与 nums2，其中nums1的元素是nums2的子集。在nums2中寻找大于nums1中对应位置且距离最近的元素。如果对应位置不存在这样的元素，则输出-1。Easy
  思路：用stack维护一个递减序列，当num>stack[-1] 时 弹出stack[-1]同时表示num是弹出的值的下一个大元素

class Solution(object):    def nextGreaterElement(self, findNums, nums):        """        :type findNums: List[int]        :type nums: List[int]        :rtype: List[int]        """        dmap,stack = {},[]        for num in nums:            while stack and stack[-1]

• [Leetcode 503] ：求循环数组的最近较大值。Medium
  思路：其实和前一题一样，因为是循环数组，对数组进行拼接再操作即可

class Solution(object):    def nextGreaterElements(self, nums):        """        :type nums: List[int]        :rtype: List[int]        """        size,stack = len(nums),[]        ret = [-1]*size        nums = nums+nums        for idx,num in enumerate(nums):            while stack and nums[stack[-1]]

• [Leetcode 682] ：一个数组，数字字符表示当局得分，’C’表示上一局得分无效,’D’表示上一局得分翻倍，‘+’表示得分前两局之和，求总的分数，Easy

class Solution(object):    def calPoints(self, ops):        """        :type ops: List[str]        :rtype: int        """        stack = []        for op in ops:            if op=='C':                stack.pop()            elif op=='D':                stack.append(stack[-1]*2)            elif op=='+':                stack.append(stack[-1]+stack[-2])            else:                stack.append(int(op))        return sum(stack)

• [Leetcode 735] ：行星碰撞问题。+,-表示方向，大小表示质量，若发生碰撞，则保留大质量的行星，若两行星质量相同，则一起消失。Medium

class Solution(object):    def asteroidCollision(self, asteroids):        """        :type asteroids: List[int]        :rtype: List[int]        """        stack = []        for asteroid in asteroids:            flag = True            while(stack and stack[-1]>0 and asteroid<0 and flag):                if -asteroid>stack[-1]: stack.pop()                else:                    flag = False                    if -asteroid==stack[-1]: stack.pop()            if flag:  stack.append(asteroid)        return stack

• [Leetcode 636] ：给定一组函数调用日志，格式为”function_id:start_or_end:timestamp”，函数可以递归。求每个函数调用的总时长。Medium
  思路：这题其实巧妙在栈顶元素的变化。如果有新的函数进来，可以先计算stack[-1] 的调用时间，如果当前函数执行完毕，trick在stack[-1][1] = logtime+1，即记录成当前stack[-1]重新执行的时间

class Solution(object):    def exclusiveTime(self, n, logs):        """        :type n: int        :type logs: List[str]        :rtype: List[int]        """        stack,ans = [],[0 for i in range(n)]        for log in logs:            logname,state,logtime = log.split(':')            logname,logtime = int(logname),int(logtime)            if state == 'start':                if len(stack):                    ans[stack[-1][0]]+=logtime-stack[-1][1]                stack.append([logname,logtime])            else:                lastitem = stack.pop()                ans[lastitem[0]]+=logtime-lastitem[1]+1                if len(stack):                    stack[-1][1]=logtime+1        return ans

• [Leetcode 232] ：用栈实现队列，剑指原题。Easy
  思考：栈FILO，队列FIFO

class MyQueue(object):    def __init__(self):        self.stack1 = []        self.stack2 = []    def push(self, node):        self.stack1.append(node)    def pop(self):        if len(self.stack2):            return self.stack2.pop()        while(self.stack1):            self.stack2.append(self.stack1.pop())        return self.stack2.pop()    def peek(self):        if len(self.stack2):            return self.stack2[-1]        while(self.stack1):            self.stack2.append(self.stack1.pop())        return self.stack2[-1]    def empty(self):        return self.stack1==[] and self.stack2==[]

• [Leetcode 225] ：用队列数据结构来实现栈, Easy
  思路：主要是要注意到队列是先进先出，而栈是先进后出，那么top和pop操作在队列中的应用可以看成是把对首的元素加入到队尾的过程。

class MyStack(object):    def __init__(self):        """        Initialize your data structure here.        """        self.queue = []        self.size = 0    def push(self, x):        """        Push element x onto stack.        :type x: int        :rtype: void        """        self.queue.append(x)        self.size +=1    def pop(self):        """        Removes the element on top of the stack and returns that element.        :rtype: int        """        for i in range(self.size-1):            self.queue.append(self.queue.pop(0))        self.size -=1        return self.queue.pop(0)    def top(self):        """        Get the top element.        :rtype: int        """        for i in range(self.size-1):            self.queue.append(self.queue.pop(0))        target = self.queue.pop(0)        self.queue.append(target)        return target    def empty(self):        """        Returns whether the stack is empty.        :rtype: bool        """        return self.size == 0

• [Leetcode 155] ：设计一个最小栈，剑指原题.Easy

class MinStack(object):    def __init__(self):        """        initialize your data structure here.        """        self.stack = []        self.minstack =[]    def push(self, x):        """        :type x: int        :rtype: void        """        self.stack.append(x)        if len(self.minstack)==0 or self.minstack[-1][0]>x:            self.minstack.append((x,1))        elif self.minstack[-1][0] == x:            self.minstack[-1] = (x,self.minstack[-1][1]+1)    def pop(self):        """        :rtype: void        """        ans = self.stack[-1]        self.stack = self.stack[0:len(self.stack)-1]        if ans == self.minstack[-1][0]:            if self.minstack[-1][1] == 1:                self.minstack.remove(self.minstack[-1])            else:                self.minstack[-1] = (ans,self.minstack[-1][1]-1)    def top(self):        """        :rtype: int        """        return self.stack[-1]    def getMin(self):        """        :rtype: int        """        return self.minstack[-1][0]

• [Leetcode 94] ：求二叉树的中序遍历结果。Medium
• [Leetcode 173] : Medium
  思路：中序遍历结果为LVR，那么压栈顺序为[RVL]然后展开

class Solution(object):    def inorderTraversal(self,root): # iterative        '''        :param root: TreeNode        :return: List[int]        '''        stack,ret = [],[]        if root == None: return []        stack.append(root)        while(stack):            query = stack.pop()            if query.left == None and query.right == None:                ret.append(query.val)            else:                if query.right:                    stack.append(query.right)                stack.append(TreeNode(query.val))                if query.left:                    stack.append(query.left)        return ret

上述的空间复杂度是O(size)，拍脑袋（其实是看别人的博客啦·）想到一个O(k)k是树深的想法，维护一个栈，从根节点开始，每次迭代地将根节点的左孩子压入栈，直到左孩子为空为止。调用next()方法时，弹出栈顶，如果被弹出的元素拥有右孩子，则以右孩子为根，将其左孩子迭代压栈。

class Solution(object):    def inorderTraversal(self,root): # iterative        '''        :param root: TreeNode        :return: List[int]        '''        stack,ret = [],[]        if root is None: return []        stack.append(root)        while(root):            if root.left:                stack.append(root.left)            root = root.left        while(stack):            root = stack.pop()            ret.append(root.val)            root = root.right            while(root):                stack.append(root)                root = root.left        return ret

• [Leetcode 144] ：求二叉树的先序遍历结果。Medium
  思路：先序遍历结果为VLR，那么压栈顺序为[RL]然后展开

class Solution(object):    def preorderTraversal(self, root):        """        :type root: TreeNode        :rtype: List[int]        """        if root == None:            return []        ret = []        stack = [root]        while(len(stack)):            query = stack.pop()            ret.append(query.val)            if query.right:                stack.append(query.right)            if query.left:                stack.append(query.left)        return ret

• [Leetcode 145] ：求二叉树的后序遍历结果。Medium
  思路：后序遍历结果为LRV，那么压栈顺序为[VRL]然后展开

class Solution(object):    def postorderTraversal(self, root):        """        :type root: TreeNode        :rtype: List[int]        """        ret = []        if root == None:            return ret        stack  = [root]        while(len(stack)):            query = stack.pop()            if query.left == None and query.right == None:                ret.append(query.val)            else:                stack.append(TreeNode(query.val))                if query.right:                    stack.append(query.right)                if query.left:                    stack.append(query.left)        return ret

• [Leetcode 103] ：二叉树按层遍历，第一行从左往右，第二行从右往左,…。Medium
  思路：加个当前层数的判断

class Solution(object):    def zigzagLevelOrder(self, root):        """        :type root: TreeNode        :rtype: List[List[int]]        """        ret, stack, step = [], [], 0        if root == None: return ret        stack.append(root)        while (stack):            tmpstack = []            tmp = []            for node in stack:                tmp.append(node.val)                if node.left:                    tmpstack.append(node.left)                if node.right:                    tmpstack.append(node.right)            if step % 2:                tmp = tmp[::-1]            ret.append(tmp[:])            step += 1            stack = tmpstack[:]        return ret

• [Leetcode 150] ：后缀表达式（逆波兰表达式）求值，Medium
  注意两个异号值相处时有个坑- -

class Solution(object):    def evalRPN(self, tokens):        """        :type tokens: List[str]        :rtype: int        """        stack = []        for token in tokens:            if token in ['+','-','*','/']:                num1 = stack.pop()                num2 = stack.pop()                if token=='+':                     stack.append(num1+num2)                elif token == '-':                    stack.append(num2-num1)                elif token == '*':                    stack.append(num1*num2)                else:                    if num1*num2<0:                        ans = -(-num2/num1)                    else:                        ans = num2/num1                    stack.append(ans)            else:                stack.append(int(token))        return stack[0]

• [Leetcode 331] ：判断一个字符串是否是某个二叉树的先序遍历序列化格式，Medium
  思考：用一个stack维护当前结点的状态 0：结点左右孩子结点格式未满足，1：结点的右孩子结点格式已满足 2：结点的左右结点格式已满足，这时候需要pop，同时把stack[-1]+=1

class Solution(object):    def isValidSerialization(self, preorder):        """        :type preorder: str        :rtype: bool        """        order = preorder.split(',')        if order == [] or order == ['#']: return True        stack,flag = [],True        for token in order:            if token == '#':                if stack == []: return False                stack[-1]+=1                while(stack and stack[-1]==2):                    stack.pop()                    if stack: stack[-1]+=1            else:                if stack == []:                    if flag:                         stack = [0]                        flag = False                    else:                        return False                else:                    stack.append(0)        return stack == []

• [Leetcode 71] ：路径简化,Medium

class Solution(object):    def simplifyPath(self, path):        """        :type path: str        :rtype: str        """        path_array = path.split('/')        stack = []        for item in path_array:            if item not in ['','.','..']:                stack.append(item)            elif item == '..' and len(stack):                stack.pop(-1)        if stack ==[]:            return '/'        else:            return '/'+'/'.join(stack)

• [Leetcode 20] ：判断括号匹配是否合法，Easy

class Solution(object):    def isValid(self, s):        """        :type s: str        :rtype: bool        """        stack = []        dic = {
  ')':'(',']':'[','}':'{'}        for i in s:            if i in ['(','[','{']:                stack.append(i)            elif i in [')',']','}']:                if len(stack) and stack[-1]==dic[i]:                    stack.pop()                else:                    return False            else:                return False        if len(stack)==0:            return True        return False

• [Leetcode 341] ：给定一个嵌套的整数列表，实现一个迭代器将其展开。每一个元素或者是一个整数，或者是一个列表 – 其元素也是一个整数或者其他列表。Medium

class NestedIterator(object):    def __init__(self, nestedList):        """        Initialize your data structure here.        :type nestedList: List[NestedInteger]        """        def getList(query):            query=query.getList()            ans = []            for i in range(len(query)):                if query[i].isInteger():                    ans += [query[i]]                else:                    ans += getList(query[i])            return ans        self.stack = []        for i in range(len(nestedList)):            if nestedList[i].isInteger():                self.stack += [nestedList[i]]            else:                self.stack += getList(nestedList[i])    def next(self):        """        :rtype: int        """        ret = self.stack.pop(0)        return ret.getInteger()    def hasNext(self):        """        :rtype: bool        """        return self.stack !=[]

• [Leetcode 456] ：判断数组中是否包含132形式，Medium

class Solution(object):    def find132pattern(self, nums):        """        :type nums: List[int]        :rtype: bool        """        size,third,stack =len(nums),None,[]        for i in range(size):            num = nums[size-1-i]            if third and num < third:                return True            else:                while(len(stack) and num>stack[-1]):                    third = stack[-1]                    stack.pop()            stack.append(num)        return False

• [Leetcode 402] ：从字符串中移除k个字符，使得剩下的字符组成的数字最小，Medium
  思路：stack[-1]>num时移除，同时k–

class Solution(object):    def removeKdigits(self, num, k):        """        :type num: str        :type k: int        :rtype: str        """        stack = []        length = len(num)-k        for i in num:            while len(stack) and k>0 and stack[-1]>i:                stack.pop()                k-=1            stack.append(i)        ret = ''        flag = True        for i in range(length):            if flag:                if stack[i]!='0':                    ret+=stack[i]                    flag =False            else:                ret +=stack[i]        if len(ret)==0:            return '0'        return ret

• [Leetcode 394] ：字符串解码，Medium

class Solution(object):    def decodeString(self, s):        """        :type s: str        :rtype: str        """        digit = None        stack = []        for si in s:            if si>='0' and si<='9':                if digit==None:                    digit=int(si)                else:                    digit=digit*10+int(si)            elif si=='[':                if digit!=None:                    stack.append(digit)                    digit=None                stack.append(si)            elif si==']':                tmp = ''                while(stack and stack[-1]!='['):                    tmp = stack[-1]+tmp                    stack.pop()                stack[-1] = tmp                if len(stack)>1 and isinstance(stack[-2],int):                    stack[-2] = stack[-2]*stack[-1]                stack.pop()            else:                stack.append(si)        return ''.join(stack)

• [Leetcode 385]

class Solution(object):    def deserialize(self, s):        """        :type s: str        :rtype: NestedInteger        """        stack = []        sigma, negmul = None, 1        for c in s:            if c == '-':                negmul = -1            elif '0' <= c <= '9':                sigma = (sigma or 0) * 10 + int(c)            elif c == '[':                stack.append(NestedInteger())            else:                if sigma is not None:                    stack[-1].add(NestedInteger(sigma * negmul))                    sigma, negmul = None, 1                if c == ']':                    top = stack.pop()                    if stack: stack[-1].add(top)                    else: return top        return NestedInteger((sigma or 0) * negmul)

• [Leetcode 726] ：将分子式展开，返回各原子的个数，Hard
  思路：字符串处理，分情况讨论

import collectionsclass Solution(object):    def countOfAtoms(self, formula):        """        :type formula: str        :rtype: str        """        size = len(formula)        def getDigit(idx):            cnt = 0            while (idx < len(formula) and formula[idx].isdigit()):                cnt = cnt*10+int(formula[idx])                idx += 1            idx-=1            if cnt:                return cnt,idx            else:                return 1,idx        stack = [collections.defaultdict(int)]        idx = 0        while(idx
   
    ='A' and token<='Z':                ch = token                idx+=1                while (idx < len(formula) and formula[idx]>='a' and formula[idx]<='z'):                    ch+=formula[idx]                    idx += 1                cnt,idx = getDigit(idx)                stack[-1][ch]=stack[-1][ch]+cnt             elif token=='(':                stack.append(collections.defaultdict(int))            elif token==')':                idx +=1                cnt,idx = getDigit(idx)                for key in stack[-1]:                    stack[-1][key] = stack[-1][key]*cnt                tstack = stack.pop()                for key in tstack:                    stack[-1][key]+=tstack[key]            idx+=1        ret = ''        for x in sorted(stack[-1].items(),key=lambda x:x[0]):            if x[1]!=1:                ret+=x[0]+str(x[1])            else:                ret+=x[0]        return ret
   

转载地址：http://mfqmi.baihongyu.com/