栈基础题20、496、232

20. 有效的括号

 1 class Solution:
 2     #遍历完字符串后，栈是空的，说明全部匹配了
 3     def isValid(self, s: str) -> bool:
 4         stack = []
 5         #剪枝
 6         if len(s) % 2 != 0:
 7             return False
 8 
 9         for item in s:
10             if item == '(':
11                 stack.append(')')
12             elif item == '[':
13                 stack.append(']')
14             elif item == '{':
15                 stack.append('}')
16             #第三种情况栈已经为空了，右边括号多了
17             #第二种情况是括号不匹配
18             elif not stack or stack[-1] != item:
19                 return False
20             else:
21                 stack.pop()
22         #第一种情况，遍历完字符串后，栈不为空，还有右括号在栈里，说明原字符串中左括号多余
23         return True if not stack else False
24

        #第二种：字典快一点
        stack = []
        mapping = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        for item in s:
            if item in mapping.keys():
                stack.append(mapping[item])
            elif not stack or stack[-1] != item: 
                return False
            else: 
                stack.pop()
        return True if not stack else False

单调栈 

496. 下一个更大元素 I

739. 每日温度

 1 class Solution:
 2     def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
 3         answer = [0]*len(temperatures)
 4         stack = [0]
 5         for i in range(1,len(temperatures)):
 6             # 情况一和情况二 当前元素比栈里元素小于等于时加入栈中
 7             if temperatures[i]<=temperatures[stack[-1]]:
 8                 stack.append(i)
 9             # 情况三 是一个持续过程，当前元素比栈顶元素大的时候，弹出栈顶元素，计算结果，并将当前元素加入栈里
10             else:
11                 while len(stack) != 0 and temperatures[i]>temperatures[stack[-1]]:
12                     answer[stack[-1]]=i-stack[-1]
13                     stack.pop()
14                 stack.append(i)
15 
16         return answer
17 
18         #精简版
19         # answer = [0]*len(temperatures)
20         # stack = []
21         # for i in range(len(temperatures)):
22         #     while len(stack)>0 and temperatures[i] > temperatures[stack[-1]]:
23         #         answer[stack[-1]] = i - stack[-1]
24         #         stack.pop()
25         #     stack.append(i)
26         # return answer