健身达人每日步数

题目分析

给定 $n$ 天的步数记录，如果某天的步数严格大于其后某一天步数的两倍，则该天称为"突破日"。求突破日的总数。

换句话说，第 $i$ 天是突破日当且仅当存在 $j > i$ 使得 $a_i > 2 \times a_j$ ，等价于 $a_i > 2 \times \min(a_{i+1}, a_{i+2}, \dots, a_{n-1})$ 。

思路

后缀最小值

对于每一天，我们需要判断它的步数是否严格大于后面所有天中最小步数的两倍。暴力做法对每个位置都扫描后面所有元素求最小值，时间复杂度 $O(n^2)$ 。

优化方法很直观：从右往左遍历，维护一个后缀最小值 suffix_min。对于当前位置 $i$ （ $i < n-1$ ），如果 $a_i > 2 \times \text{suffix\_min}$ ，则第 $i$ 天是突破日。判断完成后，将 $a_i$ 纳入后缀最小值的更新。

注意最后一天没有后续天，不可能是突破日。另外需要特判 $n = 0$ 的边界情况。

以样例 1 验证： $a = [2, 4, 3, 5, 1]$ ，从右往左：

$i=4$ ： $\text{suffix\_min} = 1$ ，无后续天，跳过
$i=3$ ： $a_3=5 > 2 \times 1 = 2$ ，突破日， $\text{suffix\_min} = \min(1, 5) = 1$
$i=2$ ： $a_2=3 > 2$ ，突破日， $\text{suffix\_min} = \min(1, 3) = 1$
$i=1$ ： $a_1=4 > 2$ ，突破日， $\text{suffix\_min} = \min(1, 4) = 1$
$i=0$ ： $a_0=2 > 2$ ？不满足严格大于，不是突破日

结果为 $3$ ，与预期一致。

复杂度

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(n)$ ，存储输入数组（如果用流式读入可以做到 $O(1)$ ）

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int ans = 0;
    int suffix_min = INT_MAX;
    // 从右往左扫描，维护后缀最小值
    for (int i = n - 1; i >= 0; i--) {
        if (i < n - 1 && a[i] > 2 * suffix_min) {
            ans++;
        }
        suffix_min = min(suffix_min, a[i]);
    }
    printf("%d\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        int ans = 0;
        int suffixMin = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (i < n - 1 && a[i] > 2 * suffixMin) {
                ans++;
            }
            suffixMin = Math.min(suffixMin, a[i]);
        }
        System.out.println(ans);
    }
}

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = [int(data[i + 1]) for i in range(n)]

    ans = 0
    suffix_min = float('inf')
    for i in range(n - 1, -1, -1):
        if i < n - 1 and a[i] > 2 * suffix_min:
            ans += 1
        suffix_min = min(suffix_min, a[i])

    print(ans)

if __name__ == '__main__':
    main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    if (n <= 0) {
        console.log(0);
        return;
    }
    const a = lines[1].split(' ').map(Number);

    let ans = 0;
    let suffixMin = Infinity;
    for (let i = n - 1; i >= 0; i--) {
        if (i < n - 1 && a[i] > 2 * suffixMin) {
            ans++;
        }
        suffixMin = Math.min(suffixMin, a[i]);
    }
    console.log(ans);
});