Easy

题目描述

句子是由单个空格分隔的一系列标记，没有前导或尾随空格。每个标记要么是由数字 0-9 组成的正数（没有前导零），要么是由小写英文字母组成的单词。

例如，“a puppy has 2 eyes 4 legs” 是一个有七个标记的句子：“2” 和 “4” 是数字，其他标记如 “puppy” 是单词。

给定一个表示句子的字符串 s，你需要检查 s 中的所有数字是否从左到右严格递增（即除了最后一个数字外，每个数字都严格小于其右边的数字）。

如果是这样，返回 true，否则返回 false。

示例 1：

输入：s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
输出：true
解释：s 中的数字是：1, 3, 4, 6, 12。
它们从左到右严格递增：1 < 3 < 4 < 6 < 12。

示例 2：

输入：s = "hello world 5 x 5"
输出：false
解释：s 中的数字是：5, 5。它们不是严格递增的。

示例 3：

输入：s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
输出：false
解释：s 中的数字是：7, 51, 50, 60。它们不是严格递增的。

约束：

  • 3 <= s.length <= 200
  • s 由小写英文字母、空格和数字 0-9 组成
  • s 中的标记数在 2 到 100 之间
  • s 中的标记由单个空格分隔
  • s 中至少有两个数字
  • s 中的每个数字都是小于 100 的正数，没有前导零
  • s 不包含前导或尾随空格

解题思路

这道题的核心思路是解析字符串，提取其中的数字，并检查这些数字是否严格递增。

解题步骤：

  1. 字符串分割：将输入字符串按空格分割成多个标记（token）
  2. 数字识别：遍历每个标记，判断是否为数字。可以通过检查第一个字符是否为数字来判断
  3. 严格递增检查：维护一个变量记录前一个数字的值，每当遇到新数字时，比较它是否严格大于前一个数字

实现要点：

  • 使用字符串分割功能将句子拆分为单词
  • 对于每个单词，检查第一个字符是否为数字来判断是否为数字标记
  • 将数字字符串转换为整数进行比较
  • 如果某个数字不大于前一个数字，立即返回 false

时间复杂度分析：

  • 需要遍历所有标记一次，每个标记的处理时间是常数
  • 总体时间复杂度为 O(n)，其中 n 是字符串长度

这种方法简洁高效，通过一次遍历即可完成判断。

代码实现

class Solution {
public:
    bool areNumbersAscending(string s) {
        istringstream iss(s);
        string token;
        int prevNum = 0;
        
        while (iss >> token) {
            if (isdigit(token[0])) {
                int num = stoi(token);
                if (num <= prevNum) {
                    return false;
                }
                prevNum = num;
            }
        }
        
        return true;
    }
};

class Solution:
    def areNumbersAscending(self, s: str) -> bool:
        tokens = s.split()
        prev_num = 0
        
        for token in tokens:
            if token[0].isdigit():
                num = int(token)
                if num <= prev_num:
                    return False
                prev_num = num
        
        return True

public class Solution {
    public bool AreNumbersAscending(string s) {
        string[] tokens = s.Split(' ');
        int prevNum = 0;
        
        foreach (string token in tokens) {
            if (char.IsDigit(token[0])) {
                int num = int.Parse(token);
                if (num <= prevNum) {
                    return false;
                }
                prevNum = num;
            }
        }
        
        return true;
    }
}

var areNumbersAscending = function(s) {
    const tokens = s.split(' ');
    let prevNum = 0;
    
    for (const token of tokens) {
        if (token[0] >= '0' && token[0] <= '9') {
            const num = parseInt(token);
            if (num <= prevNum) {
                return false;
            }
            prevNum = num;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串中的每个字符一次，其中 n 是字符串长度
空间复杂度O(k)需要存储分割后的标记，其中 k 是标记的数量，在最坏情况下为 O(n)

相关题目