题目描述

给定一个混合字符串 s，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1。

混合字符串 由小写英文字母和数字组成。

样例

输入：s = "dfa12321afd"
输出：2
解释：出现在 s 中的数字包括 [1, 2, 3]。第二大的数字是 2。

输入：s = "abc1111"
输出：-1
解释：出现在 s 中的数字只包含 [1]。没有第二大的数字。

限制

• 1 <= s.length <= 500
• s 只包含小写英文字母和（或）数字。

算法

(暴力枚举) $O(n)$

1. 找到字符串中所有的数字并存下来每个数字出现的次数。
2. 从 9 开始倒序找到第二大的数字。

时间复杂度

• 遍历字符串一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int secondHighest(string s) {
        const int n = s.size();
        vector<int> seen(10, 0);

        for (int i = 0; i < n; i++)
            if (s[i] >= '0' && s[i] <= '9')
                seen[s[i] - '0']++;

        bool first = false;
        for (int i = 9; i >= 0; i--)
            if (seen[i] > 0) {
                if (!first) first = true;
                else return i;
            }
        return -1;
    }
};