LeetCode 678. 有效的括号字符串

Categories:

Tags:

题目描述
思路分析
1. 解法一：贪心维护可行区间（推荐）
相似题目

题目描述

✅ 678. 有效的括号字符串

思路分析

解法一：贪心维护可行区间（推荐）

核心思路：

用 minOpen 表示当前可能的最小左括号数，maxOpen 表示最大左括号数。

遇到 (：两者都加一；遇到 )：两者都减一；遇到 *：minOpen 可减一、maxOpen 可加一。

任意时刻若 maxOpen < 0 直接失败；最后要求 minOpen == 0。

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度。

空间复杂度：O(1)，仅使用常数额外变量。

class Solution {
    public boolean checkValidString(String s) {
        int minOpen = 0;
        int maxOpen = 0;

        // minOpen/maxOpen 表示可能的左括号数量区间
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen = Math.max(0, minOpen - 1);
                maxOpen--;
            } else {
                minOpen = Math.max(0, minOpen - 1);
                maxOpen++;
            }

            if (maxOpen < 0) {
                return false;
            }
        }

        return minOpen == 0;
    }
}

func checkValidString(s string) bool {
    minOpen := 0
    maxOpen := 0

    // minOpen/maxOpen 表示可能的左括号数量区间
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c == '(' {
            minOpen++
            maxOpen++
        } else if c == ')' {
            if minOpen > 0 {
                minOpen--
            }
            maxOpen--
        } else {
            if minOpen > 0 {
                minOpen--
            }
            maxOpen++
        }

        if maxOpen < 0 {
            return false
        }
    }

    return minOpen == 0
}

相似题目

题目	难度	考察点
20. 有效的括号	简单	栈匹配
32. 最长有效括号	困难	动态规划/栈
22. 括号生成	中等	回溯
1249. 移除无效的括号	中等	栈+贪心
921. 使括号有效的最少添加	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/15168732