栈

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

class Solution:
    def isValid(self, s: str) -> bool:
        hashmap={'(':')','{':'}','[':']'}
        stack=[]
        for i in s:
            if i in hashmap: stack.append(i)
            else:
                if not stack: return False
                elif i!=hashmap[stack.pop()]: return False
        return not stack

#注意：not stack是stack为空，不是stack==None

#其它版本：

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for c in s:
            if c in dic: stack.append(c)
            elif dic[stack.pop()] != c: return False 
        return len(stack) == 1

456. 132 模式

是否存在坐标 a < b < c 使 nums[a] < nums[c] <nums [b]

# 从右向左维护一个单调递减的栈

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        c = float('-inf')
        
        for a in range(len(nums)-1, -1, -1): 
            if nums[i] < c:
                return True
            while stack and nums[a] > stack[-1]:
                c = stack.pop()        # c 总为栈出来的最大的数
            stack.append(nums[a])
            
        return False

496. 下一个更大元素 I

思路：单调栈 + 哈希表

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d = {}
        stack = []
        for num in nums2:
            if not stack or num <= stack[-1]:
                stack.append(num)
            else:
                while stack and stack[-1] < num:
                    d[stack.pop()] = num
                stack.append(num)

        res = [d.get(num, -1) for num in nums1]

        return res

678. 有效的括号字符串

栈抽象成 贪心 了

# 出错的情况：
# 多的 “ ）”：max_cnt < 0 处排除了
# 多的 “（ ”：min_cnt == 0 处排除了

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_cnt = 0    # 栈中（ 最小个数
        max_cnt = 0    # 栈中（ 最大值
        for c in s:
            if c == "(":
                min_cnt += 1
                max_cnt += 1
            elif c == ")":
                min_cnt = max(min_cnt-1, 0)
                max_cnt -= 1
                if max_cnt < 0:
                    return False
            else:
                min_cnt = max(min_cnt-1, 0)
                max_cnt += 1
        return min_cnt == 0

1996. 游戏中弱角色的数量

返回攻击防御都低于某个角色的角色数目。

class Solution:
    def numberOfWeakCharacters(self, p: List[List[int]]) -> int:
        p.sort(key = lambda x:[x[0],-x[1]])
        print(p)
        stack = []
        res = 0
        
        for a, d in p:
            while stack and stack[-1][0]<a and stack[-1][1]<d:   #总是相同攻击力下的最高防御加入栈，666
                stack.pop()
                res += 1
            stack.append((a,d))
            
        return res

剑指 Offer 30. 包含min函数的栈

再使用一个非严格降序的栈

class MinStack:

    def __init__(self):
        self.stack = []
        self.helper = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.helper or x <= self.helper[-1]:
            self.helper.append(x) 

    def pop(self) -> None:
        if self.stack.pop() == self.helper[-1]:
            self.helper.pop()

    def top(self) -> int:
        return self.stack[-1]

    def min(self) -> int:
        return self.helper[-1]