有效的括号
解法一
使用栈保存符号的左边框
如果出现有边框就与栈顶符号进行匹配
如果匹配失败则return false
注意：对栈的使用要注意判空
class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); for(int i = 0;i < s.length();i++){ char cur = s.charAt(i); // 当前字符 if(cur == '[' || cur == '{' || cur == '(')stack.add(cur); else { if(stack.isEmpty()) return false; // 如果当前为空 char t = stack.pop(); if(cur == ']' && t != '[') return false; if(cur == ')' && t != '(') return false; if(cur == '}' && t != '{') return false; } } if(!stack.isEmpty()) return false; return true; } }
最长有效括号
解法一
遍历
首先判断长度为len的字符串是否满足
然后判断长度为len-1的字符串是否满足
然后一直到判断长度为2的字符串是否满足
时间复杂度为(O(N^3))
class Solution { public int longestValidParentheses(String s) { int len = s.length(); if(len <= 1 )return 0; for(int i = len-1;i >= 1;i--){ // 当前匹配字符串的长度 for(int j = 0;j < len-i;j++){ //从哪里开始匹配 if(isVaild(s,j,j+i)){ return i+1; // 因为i比长度少了1 } } } return 0; } public Boolean isVaild(String s,int l,int r){ Stack<Character> stack = new Stack<Character>(); for(int i = l;i <= r;i++){ if(s.charAt(i) == '(') stack.add(s.charAt(i)); else { if(stack.isEmpty()) return false; if(stack.pop() != '(') return false; } } return stack.isEmpty(); } }
解法二
使用栈
知世参考这位大佬的文章
class Solution { public int longestValidParentheses(String s) { int res = 0; Stack<Integer> stack = new Stack<Integer>(); int start = 0; for(int i = 0;i < s.length();i++){ if(s.charAt(i) == '(') stack.add(i); else{ if(stack.isEmpty()){ start = i+1; }else{ stack.pop(); if(stack.isEmpty()){ // 说明从start-i都是匹配好的 res = Math.max(res,i-start+1); }else{ // 说明现在的s.peek()后面 - i是匹配好的 res = Math.max(res,i-stack.peek()); } } } } return res; } }
解法三
使用动态规划
这就是一个最值问题
设置dp[i] 为以s.charAt(i)结尾的字符串的最长有效括号的长度
所以当s.charAt(i)== '('时候，dp[i] = 0
**
注意：**边界问题多判断是否到-1了所以有下面几种情况
class Solution { public int longestValidParentheses(String s) { int len = s.length(); int res = 0; if(len <= 1) return 0; int dp[] = new int[len]; //dp[i] 表示以s.charAt(i) 结尾的字符串的长度 for(int i = 1;i < len;i++){ //s,charAt(i) == '('则为 0 if(s.charAt(i) == ')'){ if(s.charAt(i-1) == '('){ // 说明是这种情况 ()() dp[i] = (i-2>=0?dp[i-2]:0) + 2; }else if(i-dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == '('){ dp[i] = 2 + dp[i-1] + (i-dp[i-1]-2 >= 0 ?dp[i-dp[i-1]-2]:0); } } res = Math.max(res,dp[i]); } return res; } }
解法四
使用left保存左括号的数量
使用right保存右括号的数量
如果left < right 说明右括号多了，说明这里已经与后面的断开了，后面的不会在这里以及前面的存在匹配直接left == right ==0
如果left == right，那么这时候匹配的长度就是2 * right
但是存在可能left 一直 大于right，那么这样就可以从后往前遍历解决问题
class Solution { public int longestValidParentheses(String s) { int res = 0; int left = 0,right = 0; for(int i = 0;i < s.length();i++){ if(s.charAt(i) == '('){ left++; }else{ right++; } if(left == right){ res = Math.max(res,2*right); } if(left < right){ left = right = 0; } } left = right = 0; for(int i = s.length()-1;i >= 0;i--){ if(s.charAt(i) == ')'){ left++; }else{ right++; } if(left == right){ res = Math.max(res,2*right); } if(left < right){ left = right = 0; } } return res; } }
最小栈
解法一
额外维护一个最小栈
class MinStack { Stack<Integer> s1 = null; Stack<Integer> min = null; public MinStack() { s1 = new Stack<Integer>(); min = new Stack<Integer>(); } public void push(int val) { s1.add(val); if(min.isEmpty()){ min.add(val); }else{ int t = min.peek(); min.add(t > val?val:t); } } public void pop() { s1.pop(); min.pop(); } public int top() { return s1.peek(); } public int getMin() { return min.peek(); } }
