1420. Build Array Where You Can Find The Maximum Exactly K Comparisons¶
题目信息¶
- 题号:
1420
- 难度:
Hard
- 主题:
动态规划、计数、前缀最大值
- 原题:
- 重点:
数组长度为
n、元素范围为[1,m];从左扫描时每遇到新的严格最大值,搜索成本增加一,统计成本恰为k的数组
题目重述¶
构造长度为 n 的整数数组,每个元素都位于 [1,m]。从左到右扫描数组,初始最大值为空;每当当前元素严格大于之前所有元素时,搜索成本增加 1。
请统计搜索成本恰好为 k 的数组数量,并返回结果对 10^9 + 7 取模后的值。
1 <= n, m <= 50,1 <= k <= n。
自建示例¶
成本为一表示首元素之后不再出现更大值:
输入:n = 2, m = 3, k = 1
输出:6
解释:首元素分别为 1、2、3 时,第二项可选数量为 1、2、3,共六个数组。
数组长度不足以产生指定次数的新最大值时答案为零:
输入:n = 1, m = 2, k = 2
输出:0
解释:只有一个元素,搜索成本只能为一。