LeetCode-栈和队列

LeetCode84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
递增栈

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack = []
        heights.append(0)
        i = 0
        res = 0
        while i<len(heights):
            if not stack or heights[stack[-1]]<=heights[i]:
                stack.append(i)
            else:
                cur = stack.pop()
# 此时的栈顶元素的位置是从cur开始向左数，第一个小于heights[cur]的位置，
# i是从cur开始向右数，第一个小于heights[cur]的位置
                width = i if not stack else i-stack[-1]-1
                res = max(res,heights[cur]*width)
                continue
            i += 1
        return res

LeetCode85. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
递增栈

class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        res  = 0
        m = len(matrix)
        if m == 0:return 0
        n = len(matrix[0])
        height = [0]*(n+1)
        for i in range(m):
            j = 0
            stack = []
            com = True
            while j < n+1:
                if com:
                    height[j] = 1+height[j] if j<n and matrix[i][j]=='1' else 0
                    com = False
                if not stack or height[stack[-1]]<=height[j]:
                    stack.append(j)
                else:
                    cur = stack.pop()
                    width = j if not stack else j - stack[-1]-1
                    res = max(res,height[cur]*width)
                    continue
                j += 1
                com = True
        return res

leetcode150 逆波兰数

代码在leetcode.com过了，leetcode-cn.com没过。。

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        oper = ['+','-','*','/']
        for token in tokens:
            if token not in oper:
                stack.append(token)
            else:
                p2 = int(stack.pop())
                p1 = int(stack.pop())
                if token == '+':
                    res = p1+p2
                elif token == '-':
                    res = p1-p2
                elif token == '*':
                    res = p1*p2
                else:
                    res = int(p1/p2)
                stack.append(str(res))
        res = stack.pop()
        return int(res)

LeetCode224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        p = self.infix_2_postfix(s)
        return self.evalRPN(p)
    def infix_2_postfix(self,s):
    # 前缀表达式转后缀表达式
        s = s+'#'
        # 定义运算符栈内和栈外的优先级
        isp = {'(':1,"*":5,"/":5,'%':5,'+':3,'-':3,')':6,'#':0}
        icp = {'(':6,"*":4,"/":4,'%':4,'+':2,'-':2,')':1,'#':0}
        stack, res =  ['#'],[]
        i,num,is_num = 0,0,False
        while stack:
            if s[i] == ' ':
                i += 1
            elif s[i].isdigit():
                num = num*10 + int(s[i])
                is_num = True
                i += 1
            else:
                if is_num:
                    res.append(str(num))
                    num = 0
                    is_num = False
                if icp[s[i]]>isp[stack[-1]]:
                    stack.append(s[i])
                    i += 1
                elif icp[s[i]]<isp[stack[-1]]:
                    res.append(stack.pop())
                else:
                    if stack.pop() == '(':
                        i += 1
        return res
    def evalRPN(self, tokens):
    # 后缀表达（逆波兰数）计算结果
        stack = []
        oper = ['+','-','*','/']
        for token in tokens:
            if token not in oper:
                stack.append(token)
            else:
                p2 = int(stack.pop())
                p1 = int(stack.pop())
                if token == '+':
                    res = p1+p2
                elif token == '-':
                    res = p1-p2
                elif token == '*':
                    res = p1*p2
                else:
                    res = int(p1/p2)
                stack.append(str(res))
        res = stack.pop()
        return int(res)

LeetCode32 最长有效括号

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []
        res = 0
        start = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                if stack:
                    stack.pop()
                    res = max(res,i-start+1) if len(stack) == 0 else max(res,i - stack[-1])
                else:
                    start = i+1
        return res