企业官网建设流程全解析

题目链接：921. 使括号有效的最少添加（中等）

算法原理：

解法：一次遍历

0ms击败100.00%

时间复杂度O(N)

思路就很简单，遍历过程中：

①先遇到 (，后遇到 )：说明这能凑成一个合法的 ()，不用管

我们就单纯用 cnt 记录就行，遇到 ( cnt++，遇到 ) cnt--

②先遇到 )（前面的()都能抵消掉，cnt=0）：这时我们肯定需要在左边某个位置加上 (，所以直接在结果 ret 上累加

最终结果就是 ret+cnt（因为cnt 必然>=0，所以不用绝对值）

Java代码：

class Solution { //921. 使括号有效的最少添加 public int minAddToMakeValid(String s) { int cnt=0,ret=0; for(char c:s.toCharArray()){ if(c=='(') cnt++; else{ if(cnt==0){ ret++; }else cnt--; } } return ret+cnt; } }