A.每日一题：1541. 平衡括号字符串的最少插入次数

题目链接1541. 平衡括号字符串的最少插入次数中等算法原理解法一次遍历8ms击败99.72%时间复杂度O(N)核心思路遍历 s 的过程中用一个变量 left 记录当前尚未配对的左括号的个数①如果 s[i] 是左括号把 left 增加 1②如果 s[i] 是右括号1左右括号配对如果 left0left 减少 1如果 left 0 就需要补上一个左括号2因为每对的右括号要连续两个所以还要检查 s[i1] 是不是右括号如果是就跳过 s[i1]如果不是就需要再补一个右括号③遍历结束后如果 left0说明有未配对的左括号需要补上 2×left 个右括号Java代码class Solution { //1541. 平衡括号字符串的最少插入次数 public int minInsertions(String ss) { char[] sss.toCharArray(); int ns.length; int left0; int ret0; for(int i0;in;i){ if(s[i]() left; else{ if(left0) left--;//左右括号配对 else ret;//右括号太多了补一个左括号 //必须连续两个判断s[i1]是否是 if(i1ns[i1])) i;//跳过下一个 else ret;//补一个右括号 } } //左括号太多了补上缺失的右括号 return retleft*2; } }