32-最長有效括号

題目

給你一個隻包含 ‘(’ 和 ‘)’ 的字元串，找出最長有效（格式正确且連續）括号子串的長度。

示例 1：

輸入：s = “(()”

輸出：2

解釋：最長有效括号子串是 “()”

示例 2：

輸入：s = “)()())”

輸出：4

解釋：最長有效括号子串是 “()()”

示例 3：

輸入：s = “”

輸出：0

題解一 動态規劃

class Solution {
    public int longestValidParentheses(String s) {
        if(s.length()==0){
            return 0;
        }
        int[] dp=new int[s.length()];
        int maxNum=0;//通過兩兩比較，得出dp數組中最大的數
        for(int i=1;i<dp.length;i++){//i=0的時候肯定是0！
            if(s.charAt(i)==')'){//(肯定為0，就不用算了
                if(s.charAt(i-1)=='('){
                    dp[i]=(i>1?dp[i-2]:0)+2;//若i=1,則直接0+2！***
                }else if((i-dp[i-1]-1)>=0&&s.charAt(i-dp[i-1]-1)=='('){//i是從0開始的，不能在索引裡判斷。而且這裡的判斷語句就有問題！i<=1了！應該把這個判斷語句放到裡面寫！
                //i-dp[i-1]>0隻是為了保證charAt存在！
                    dp[i]=dp[i-1]+((i-dp[i-1]-2)>=0?dp[i-dp[i-1]-2]:0)+2;
                }
            }
            maxNum=Math.max(dp[i],maxNum);
        }
        return maxNum;
    }
}
           

筆記：

1. 動态規劃題目分析的 4 個步驟：
   • 确定狀态
     • 研究最優政策的最後一步
     • 化為子問題
   • 轉移方程
     • 根據子問題定義得到
   • 初始條件和邊界情況
   • 計算順序
2. 最優政策的最後一步：

i−dp[i−1]−1：i減掉中間比對上的對數

考慮最後一個元素s[i]的情況：

• s[i]=’(’:dp[i]=0
• s[i]=’)’:
  • s[i-1]=’(’:dp[i]=dp[i-2]+2
  • 形如()((…)):dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2

  dp[i-1]:裡層小括号的比對數；dp[i-dp[i-1]-2]：

  因為有兩個（的時候dp就置0了，是以需要加上兩個dp的計數

1. 注意！dp[i]的判斷要在表達式内完成！并不是說>1之類的成立了就直接加2了，可能這一部分dp為0，但是還是要+2

題解二 棧

class Solution {
    public int longestValidParentheses(String s) {
        int ans=0;
        Deque<Integer> stack=new LinkedList<>();
        stack.push(-1);
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    ans=Math.max(i-stack.peek(),ans);
                }
            }
        }
        return ans;
    }
}
           

思路：

1. 注意這個思路
2. 保持棧底的元素為最後一個沒有比對上的右括号的下标。（為了保證如果第一個括号是左括号，棧底不是沒有比對上的右括号的下标，首先在棧底放入-1作為邊界條件）将每個(的下标放入棧中，作為比對，先彈出棧頂元素表示比對了)。如果遇到），檢視棧裡有沒有元素。如果棧為空，則将）的下标放入棧中，更新最後一個沒有比對上的右括号的下标。如果棧不為空，則将目前)的下标減去棧頂元素的下标，即是目前最長有效括号的長度。

3. 注意棧的初始化方法！

   Deque stack = new LinkedList();

解法三 最大最小值 貪心法

class Solution {
    public int longestValidParentheses(String s) {
        int left=0;
        int right=0;
        int maxNum=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                left+=1;
            }else{
                right+=1;
            }if(left==right){//以right為基準計算括号對的數量，maxNum記錄的是全局最大的
                maxNum=Math.max(right*2,maxNum);
            }else if(right>left){
                left=0;
                right=0;
            }
        }
        left=0;
        right=0;
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='('){
                left+=1;
            }else{
                right+=1;
            }if(left==right){//以left為基準計算括号對的數量，maxNum記錄的是全局最大的
                maxNum=Math.max(left*2,maxNum);
            }else if(right<left){
                left=0;
                right=0;
            }
        }
        return maxNum;
    }
}
           

思路：

1. 利用兩個計數器left和right。首先從左到右周遊字元串，遇到(就left+1，）就right+1.當left和right 的值相等時，記錄有效字元串的長度，并與最長的長度比較。若right>left時，則将left和right置0，重新計算。

   但是這樣計算就沒有考慮到left>right的情況，即(()這種。是以再從右向左重複差不多的操作，當left>right的時候，left和right都置0。當left=right時，更新有效字元串的長度。