What is the main approach to solve Count Number of Teams efficiently?

The most efficient method uses state transition dynamic programming combined with prefix and suffix counts to calculate all valid three-soldier teams.

Can I use a brute-force approach?

Yes, but brute-force has O(n^3) complexity and will be too slow for arrays close to 1000 elements.

Why are Binary Indexed Trees useful for this problem?

BITs allow you to maintain prefix and suffix counts of smaller or larger ratings efficiently, reducing overall computation from O(n^2) to O(n log(maxRating)).

Are soldiers allowed in multiple teams?

Yes, each soldier can be part of multiple valid teams as long as the sequence rules are satisfied.

What are common mistakes when implementing DP for this pattern?

Typical mistakes include miscounting prefix or suffix arrays, confusing index order with rating order, or forgetting to handle both increasing and decreasing sequences.

#1395

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

统计作战单位数

n 名士兵站成一排。每个士兵都有一个独一无二的评分 rating 。从中选出 3 个士兵组成一个作战单位，规则如下：从队伍中选出下标分别为 i 、 j 、 k 的 3 名士兵，他们的评分分别为 rating[i] 、 rating[j] 、 rating[k] 作战单位需满足： rating…

数组动态规划树状数组线段树

题目描述

n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。

从中选出 3 个士兵组成一个作战单位，规则如下：

从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中 0 <= i < j < k < n

请你返回按上述条件组建的作战单位的方案数。

示例 1：

输入：rating = [2,5,3,4,1]
输出：3
解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。

示例 2：

输入：rating = [2,1,3]
输出：0
解释：根据题目条件，我们无法组建作战单位。

示例 3：

输入：rating = [1,2,3,4]
输出：4

提示：

n == rating.length
3 <= n <= 1000
1 <= rating[i] <= 10^5
rating 中的元素都是唯一的

lightbulb

解题思路

方法一：枚举中间元素

我们可以枚举数组 $rating$ 中每个元素 $rating[i]$ 作为中间元素，然后统计左边比它小的元素的个数 $l$ ，右边比它大的元素的个数 $r$ ，那么以该元素为中间元素的作战单位的个数为 $l \times r + (i - l) \times (n - i - 1 - r)$ ，累加到答案中即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组 $rating$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans, n = 0, len(rating)
        for i, b in enumerate(rating):
            l = sum(a < b for a in rating[:i])
            r = sum(c > b for c in rating[i + 1 :])
            ans += l * r
            ans += (i - l) * (n - i - 1 - r)
        return ans

speed

复杂度分析

指标	值
时间	O(n \cdot \log(\text{maxRating}))
空间	O(\text{maxRating})

psychology

面试官常问的追问

外企场景

question_mark
Look for strictly increasing or decreasing sequences of length three.
question_mark
Check if the candidate avoids brute-force cubic time by counting sequences efficiently.
question_mark
Verify understanding of state transitions and prefix-suffix relationships for DP.

warning

常见陷阱

外企场景

error
Counting teams incorrectly by mixing indices instead of ratings order.
error
Using nested loops without considering DP or BIT optimizations for larger arrays.
error
Mismanaging prefix and suffix counts, leading to off-by-one errors in team totals.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count teams of length k > 3 following increasing or decreasing rules.
arrow_right_alt
Compute total teams allowing repeated ratings with adjusted DP rules.
arrow_right_alt
Find the longest strictly increasing or decreasing subsequence instead of fixed-length teams.

help

常见问题

外企场景

继续练习

#673 最长递增子序列的个数 #2407 最长递增子序列 II #1157 子数组中占绝大多数的元素