stack

20 Valid Parentheses

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

32 Longest Valid Parentheses

#Example :
#Input: ")()())"
#Output: 4
#Explanation: The longest valid parentheses substring is "()()"
class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        
        mlen = 0
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if len(stack):
                    mlen = max(mlen, i - stack[-1])
                else:
                    stack.append(i)
        return mlen

84 Largest Rectangle in Histogram

class Solution:
    # method1
    # def largestRectangleArea(self, heights: List[int]) -> int:
    #     res = 0
    #     for i in range(len(heights)):
    #         if i+1 <= len(heights)-1 and heights[i+1] >= heights[i]:
    #             continue
    #         tmp = heights[i]
    #         for j in range(i, -1, -1):
    #             tmp = min(tmp, heights[j])
    #             area = (i-j+1) * tmp
    #             res = max(area, res)
    #     return res
    
    # method2 栈
    def largestRectangleArea(self, heights: List[int]) -> int:
        res = 0
        stack = []
        for i in range(len(heights)):
            if stack == [] or stack[-1] <= heights[i]:
                stack.append(heights[i])
                #print(i, stack)
            else:
                count = 0
                while stack != [] and stack[-1] > heights[i]:
                    count += 1
                    tmp = stack.pop() * count
                    res = max(tmp, res)
                for k in range(count+1):
                    stack.append(heights[i])
                    #print(i, stack)
        count = 1
        
        while stack != []:
            res = max(res, stack.pop()*count)
            count += 1
        return res