题目链接678. 有效的括号字符串中等算法原理解法贪心时间复杂度O(N)0ms击败100.00%* 有三种选择左括号(、右括号)、空1️⃣核心思路我们没法枚举全部情况所以维护一个范围 [mn,mx]mn未匹配左括号数量的最小值把 * 尽量当成右括号减少左括号mx未匹配左括号数量的最大值把 * 尽量当成左括号增加左括号遍历到每一个字符算出当前“还剩多少左括号没匹配”的最小可能值、最大可能值只要区间 [mn,mx] 里面包含0就说明存在一种 * 的替换方案让括号合法2️⃣遍历每个字符① (新增一个左括号mnmx② )消耗一个左括号mn--mx--如果 mx0说明就算把所有 * 全当作左括号也不足以抵消这个右括号比如“)))))”直接返回 false③ *两种选择⬇️当做右括号剩余左括号减少→mn--当做左括号剩余左括号增加→mx3️⃣修正未匹配的左括号不能是负数如果 mn 算出负数代表“把 * 全部当成右括号”这个极端方案不可行直接舍弃最小值最低只能取04️⃣最终判断只要区间[mn,mx]包含0就存在一种替换 * 的方案让括号合法代码中 mn 已经被限制≥0所以只需要判断 mn0 即可Java代码class Solution { //678. 有效的括号字符串 public boolean checkValidString(String s) { int mn0;//未匹配的左括号的个数的最小值 int mx0;//未匹配的左括号的个数的最大值 for(char ch:s.toCharArray()){ if(ch(){ mn; mx; }else if(ch)){ mn--; mx--; //右括号太多了 if(mx0) return false; }else{//* mn--;//*改成右括号 mx;//*改成左括号 } //未匹配的左括号的个数不能为负数 mnMath.max(mn,0); } //最终未匹配的左括号的个数为0 return mn0; } }
