20. Valid Parentheses 有效的配对
https://leetcode.com/problems/valid-parentheses/
题目：如果一个字符串只包含‘(’，‘)、’{‘、’}‘、’[‘和’]‘，则确定输入字符串是否有效。打开括号必须由相同类型的括号关闭，则输入字符串是有效的。开括号必须按照正确的顺序关闭。注意，空字符串也被认为是有效的。
思路：新建一个栈，遍历输入字符串，如果当前字符为左半边括号，则将其压入栈中；如果当前字符为右半边括号且栈为空，则直接返回false；如果当前字符为右半边括号且栈不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回false。
32. Longest Valid Parentheses 最长有效配对
https://leetcode.com/problems/longest-valid-parentheses/
题目：给定一个只包含字符‘(’和‘)’的字符串，查找最长的有效(格式良好)括号子字符串的长度。
思路：
①使用Stack栈
②DP动态规划
class Solution { public int longestValidParentheses(String s) { // using Stack Stack<Integer> st = new Stack<>(); int result = 0; st.push(-1); for(int i = 0; i < s.length(); i++) { if(s.charAt(i) == ')' && st.size() > 1 && s.charAt(st.peek()) == '(') { st.pop(); result = Math.max(result, i - st.peek()); } else { st.push(i); } } return result; } }
class Solution { public int longestValidParentheses(String s) { // using DP int[] dp = new int[s.length()]; int result = 0, leftCount = 0; for(int i = 0; i < s.length(); i++) { if(s.charAt(i) == '(') { leftCount++; } else if(leftCount > 0) { dp[i] = dp[i - 1] + 2; dp[i] += (i - dp[i]) > 0 ? dp[i - dp[i]] : 0; result = Math.max(result, dp[i]); leftCount--; } } return result; } }
42. Trapping Rain Water 装雨水
https://leetcode.com/problems/trapping-rain-water/
题目：如果n个非负整数表示一个标高图，其中每个杆的宽度为1，则计算雨后它能装多少水。
思路：
84. Largest Rectangle in Histogram 直方图中的最大矩形
https://leetcode.com/problems/largest-rectangle-in-histogram/
题目：给定n个非负整数表示直方图的条高，其中每条的宽度为1，则在直方图中找出最大矩形的面积。
思路：
149. Max Points on a Line 直线上最大的点
https://leetcode.com/problems/max-points-on-a-line/
题目：给定二维平面上的n个点，求出位于同一直线上最大的点。
思路：
150. Evaluate Reverse Polish Notation 求解逆波兰表示法的式子
https://leetcode.com/problems/evaluate-reverse-polish-notation/
题目：用反向波兰表示法计算算术表达式的值。有效运算符是+，-，*，/。每个操作数可以是一个整数，也可以是另一个表达式。注：两个整数之间的除数应截断为零。给定的RPN表达式始终有效。这意味着表达式将始终计算为一个结果，并且不会被零运算除以任何值。
思路：