首页 > 试题广场 >

数据分析

[编程题]数据分析

热度指数：318 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出具有N个数字的数组，求长度为k的子数组中最大值的最小值。

例如数组 $[1,3,5,2,4,6]\$ ，长度为3的子数组分别为 $[1,3,\color{red}{5}], [3,\color{red}{5},2], [\color{red}{5},2,4]\$ 和 $[2,4,\color{red}{6}]\$ ，子数组最大值分别为 $[5,5,5,6]\$ ，最小值为5

你需要返回一个长度恰好为 N 的序列，第一个元素为长度为 1 的子数组的最小值，第二个元素为长度为 2 的子数组的最小值，以此类推。

示例1

输入

[1,3,5,2,4,6]

输出

[1,3,5,5,5,6]

示例2

输入

[1,2,3,4,5,6]

输出

[1,2,3,4,5,6]

备注:

注意，一个数组的子数组指的是这个数组的某个连续序列，如 [1,2] 和 [1,2,3] 都是 [1,2,3] 的子数组。

数据范围：
- 对于 30% 的数据，
- 对于 60% 的数据，
- 对于 100% 的数据，
对于 100% 的数据，数组中的数  范围为 。

算法知识视频讲解

Dear㉿You

发表于 2020-11-20 21:19:51

C 数据分析分析先看题目：最大的最小。其在做这一类的题都有一种思想。因为暴力时直接枚举区间，但是反着来，求出一个数对某一段区间的影响，拿样例举例一个数能作为最大值，区间的范围之内就不能出现大于它的任何数,设lm[i]:位于i左边第一个大于a[i]的数的位置+1 rm[i]:位于i右边第一个大于展开全文

Bernard5

发表于 2020-11-23 21:37:07

题意给定一个长度为的数组。找它的长度为的区间中的最大值，求这些所有的最大值的集合里的最小值。思路利用单调栈，对于每一个，找出来左边第一个比它大的，找出来右边第一个比它大的。并且把它们的下标分别存和里。对于每一个，它能作为最小值的最长区间已经确定了。那么就可以通过比较得到一部分长度的区间的最展开全文

ZhongHaoWang

发表于 2021-08-27 17:06:39

由于我们只需要考虑每个长度为N的子数组的最大值,因此我们枚举每个元素,记录其可以为子数组最大值的覆盖区间长度,在该区间内该元素始终为最大值；同时我们可以知道,若存在一个长度为m的子数组最大值为k,显然可以找到任意一个长度小于等于m的子数组使其最大值为k；因此我们首先通过单调栈求出每个元素的覆盖区间, 展开全文

YoungPQ

发表于 2021-08-22 10:32:03

第一步，设置维护两个数组 leftBiggerId[]、 rightBiggerId[]，返回结果为res[] 计算 leftBiggerId[i] ：在第i个元素的左边，找到一个最近的元素numbers[x]，使得numbers[x]>numbers[i]，则leftBiggerId[i]= 展开全文

问题信息

数组

难度：

0条回答 11收藏 1354浏览

通过挑战的用户

查看代码

草苺奶昔

2022-02-21 15:35:24
青椒炒牛肉

2021-11-11 15:26:41
牛逼89757号

2021-11-04 11:15:48
快手_各产品线内推

2021-11-01 22:08:18
牛客70924...

2021-10-19 22:05:38

数据分析

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题