ORID55 Stack

这两个链接的解释都非常好，你需要仔细看看
https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
https://leetcode.com/problems/longest-common-subsequence/discuss/351689/JavaPython-3-Two-DP-codes-of-O(mn)-and-O(min(m-n))-spaces-w-picture-and-analysis

1249. Minimum Remove to Make Valid Parentheses 解题报告

用什么算法？

没特殊算法，算是数据结构的灵活运用，要用stack和stringbuilder
这道题虽然并不是特别难，但是我还是没能够完全解决它。最后还是看了讨论里面的参考答案。
实际上我思路没什么问题，就是按照validate parentheses 的思路做的，用的是stack，但是我还是没能灵活运用自己学到的数据结构，stack可以用来记录当前括号的位置，并不需要记录全部的character，而讨论区里面的答案则灵活运用了这点。他用stack来记录括号出现的位置。
那么当左括号“（” 出现的时候，stack.push(i） 就可以了，因为i是当前的字母的指针，如果后面遇到右括号，把stack上面的值pop就可以了，因为他找到了对应的右括号。
那如果多余的右括号怎么办呢？

if (stack.isEmpty()) {
  sb.setCharAt(i, '*');
}

它用了stringbuilder来解决这个问题，我一开始把两个概念分开了，实际上他们完全可以结合一起用来解决这道问题
他把题目给的input整个直接放到stringbuilder里面，然后在判断是否把括弧的位置放到stack里面的时候，如果是右括弧多出来，就直接把stringbuilder里面的字母换成‘*’。然后最后再替换成“”（空串）就可以了。
下面是代码

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] chars = s.toCharArray();
        int count = 0;
        StringBuilder sb = new StringBuilder(s);
        for (int i = 0; i < sb.length(); i++) {            
            if (sb.charAt(i) == '(') {
                stack.push(i);
            }
            if (sb.charAt(i) == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    sb.setCharAt(i, '*');
                }
            }
        }
        while (!stack.isEmpty()) {
            sb.setCharAt(stack.pop(), '*');
        }        
        return sb.toString().replaceAll("\\*", "");
    }
}

时空复杂度

时间复杂度O（N）
空间复杂度O（N）（stack和stringbuilder的应用）