Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
这道题的思路应该比较简单：利用栈，遇到数字则压入栈，遇到运算符则弹出数字进行运算，完成后再压入栈。这里应该默认所有表达式都是合法的，不然还需要对合法性进行检查。
特别地，这里的除法需要特别处理。
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = [] #Python 里的列表可以直接用作栈
for s in tokens:
if s in '+-*/': #注意这里in的用法
op2 = stack.pop() #注意这里[]的用法
op1 = stack.pop()
if s == '+':
stack.append(op1+op2)
elif s == '-':
stack.append(op1-op2)
elif s == '*':
stack.append(op1*op2)
else: #注意这里对符号的处理值得学习
sign = -1 if (op1<0)^(op2<0) else 1
stack.append(abs(op1)/abs(op2) * sign)
else:
stack.append(int(s))
return stack[-1] #返回最上面一个
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
思路也不难，但是细节处理比较多。连续的可配对的（）必定夹在不可配对的（）之间。在一个栈中，遇到可配对的（），就弹出，直到栈中只剩下不可配对的（），然后考察之间最大的下标差，就知道最长的连续可配对的（）是多长了。
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
longest = 0
stack = []
for i in range(n):
if s[i] == '(':
stack.append(i)
else:
if stack: # python中判断一个列表是否为空，可以直接这样判断
if s[stack[-1]] == '(':
stack.pop()
else:
stack.append(i)
else:
stack.append(i)
if not stack: # 这里计算最大下标差的方法很值得学习
longest = n
else:
a, b = n ,0
while(stack):
b = stack[-1]
stack.pop()
longest = max(longest, a - b - 1)
a = b
longest = max(longest, a)
return longest
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
依然使用一个栈来处理配对，只有完整匹配了，才返回True class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for t in s:
if t in '([{':
stack.append(t)
else:
if not stack:
return False
else:
if t == ')' and stack[-1] == '(':
stack.pop()
elif t == ']' and stack[-1] == '[':
stack.pop()
elif t == '}' and stack[-1] == '{':
stack.pop()
else:
return False
if stack:
return False
else:
return True
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example, Given heights = [2,1,5,6,2,3], return 10.
这个方法的核心在于，要做一个将高度升序排列的栈。
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
if (not heights) or len(heights) == 0:
return 0
stack = []
preLo, hi, curH, maxA = -1, 0, 0, 0
while (hi <= len(heights)):
if len(stack) == 0 or not(hi == len(heights)) and heights[hi] > heights[stack[-1]]:
stack.append(hi)
hi = hi+1
else:
curH = heights[stack.pop()]
preLo = -1 if len(stack) == 0 else stack[-1]
maxA = max(maxA, curH * (hi - preLo -1))
return maxA