题目链接

健身达人每日步数

题目描述

一位健身达人持续记录了 天的每日步行数据。

“突破日”定义： 如果某一天的步数，严格大于其后任意一天步数的两倍，那么这一天就被称作一个“突破日”。

任务： 根据这 天的步数记录，统计出其中共有多少个“突破日”。

输入描述：

  • 第一行是一个整数 ，代表记录的总天数。
  • 第二行包含 个整数，代表从第 1 天到第 天的步数记录。

输出描述：

  • 一个整数，代表这 天中“突破日”的总数量。

解题思路

本题的目标是找出数组中有多少个元素，其值严格大于其右侧所有元素中最小值的两倍。

1. 朴素解法 (暴力枚举)

最直观的思路是严格按照定义进行检查。我们可以遍历每一天 （从第 天到第 天），然后对于每一天 ，再遍历其后的所有天 （从 到 ）。只要能找到任何一个 满足 steps[i] > 2 * steps[j]，就可以确定第 天是“突破日”，并停止内层循环，开始检查下一天。

这种方法需要两层嵌套循环，时间复杂度为 。对于 的数据规模，这个解法是可以通过的，但不是最高效的。

2. 优化解法 (后缀最小值)

我们可以对朴素解法进行优化。判断 steps[i] 是否大于其后任意一天步数的两倍，等价于判断 steps[i] 是否大于其后最小步数的两倍。

因此，一个更高效的方法是从后向前遍历数组。在逆序遍历的过程中，我们可以维护一个变量 min_so_far，用于记录到目前为止（即从当前位置到数组末尾）遇到的最小步数。

  • 当我们遍历到第 天时，min_so_far 存储的正是第 天到第 天的最小步数。
  • 这样，我们就可以在 的时间内获得判断所需的值。

算法步骤如下：

  1. 初始化“突破日”计数器 count = 0。
  2. 初始化后缀最小值 min_so_far 为数组的最后一个元素 steps[N-1]。
  3. 从倒数第二天（索引 ）开始，向前遍历到第一天（索引 ）。
  4. 对于当前第 天的步数 steps[i]：
    • 判断 steps[i] > 2 * min_so_far 是否成立。
    • 如果成立，则 count 加 1。
    • 无论是否为突破日，都需要更新 min_so_far，令 min_so_far = min(min_so_far, steps[i])，以供前一天的计算使用。
  5. 遍历结束后，count 即为所求的答案。

这种方法只需要对数组进行一次遍历，时间复杂度为 ，空间复杂度为 。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n <= 1) {
        cout << 0 << endl;
        return 0;
    }

    vector<long long> steps(n);
    for (int i = 0; i < n; ++i) {
        cin >> steps[i];
    }

    int breakthrough_count = 0;
    long long min_so_far = steps[n - 1];

    // 从倒数第二天开始向前遍历
    for (int i = n - 2; i >= 0; --i) {
        // 判断是否为突破日
        if (steps[i] > 2 * min_so_far) {
            breakthrough_count++;
        }
        // 更新后缀最小值
        min_so_far = min(min_so_far, steps[i]);
    }

    cout << breakthrough_count << endl;

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        if (n <= 1) {
            System.out.println(0);
            return;
        }

        long[] steps = new long[n];
        for (int i = 0; i < n; i++) {
            steps[i] = sc.nextLong();
        }

        int breakthroughCount = 0;
        long minSoFar = steps[n - 1];

        // 从倒数第二天开始向前遍历
        for (int i = n - 2; i >= 0; i--) {
            // 判断是否为突破日
            if (steps[i] > 2 * minSoFar) {
                breakthroughCount++;
            }
            // 更新后缀最小值
            minSoFar = Math.min(minSoFar, steps[i]);
        }

        System.out.println(breakthroughCount);
    }
}

def solve():
    n = int(input())

    if n <= 1:
        print(0)
        return
    
    steps = list(map(int, input().split()))

    breakthrough_count = 0
    # 初始化后缀最小值为最后一个元素
    min_so_far = steps[n - 1]

    # 从倒数第二个元素开始向前遍历
    for i in range(n - 2, -1, -1):
        # 判断是否为突破日
        if steps[i] > 2 * min_so_far:
            breakthrough_count += 1
        
        # 更新后缀最小值
        min_so_far = min(min_so_far, steps[i])

    print(breakthrough_count)

solve()

算法及复杂度

  • 算法：本题采用后缀最小值（Suffix Minimum）的优化思想。通过从后向前单次遍历数组，同时维护一个变量来记录当前位置之后所有元素中的最小值，从而将判断每个元素是否为“突破日”的条件检查时间复杂度从 降为 。

  • 时间复杂度：，其中 是记录的总天数。我们只需要对步数数组进行一次逆序遍历。

  • 空间复杂度：（不包括存储输入数据的空间）。我们仅使用了少数几个变量（计数器、后缀最小值）来完成计算。