有限空间试题_第1页
有限空间试题_第2页
有限空间试题_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

有限空间最新试题1.题目描述有一个长度为n的数组a，其中元素都为非负整数。定义一个区间的权值为这个区间里元素的和，而一个区间的长度为区间中元素的数量。给定一个整数l，现在需要计算a中所有长度为l的区间中，权值最小的区间的权值。2.样例输入输出输入样例：a=[1,3,2,1,4,3,1],l=3输出样例：2解释：长度为3的区间有[1,3,2],[3,2,1],[2,1,4],[1,4,3],[4,3,1]共5个，其中最小权值为2，对应区间为[1,3,2]。3.解题思路本题可以使用单调队列进行求解，具体思路如下：首先，我们可以在a数组的前l个元素中找到一个最小的数，并记录它的下标pos，然后我们可以认为这个最小的数就是长度为l的区间中最小元素了。接下来，我们从l开始往后扫描整个数组a，对于每个长度为l的区间，都可以使用上一次遍历求得的最小元素来更新最小权值。具体地，我们维护一个单调队列q，它里面储存的是区间中元素对应的下标。初始时，我们可以将q里面加入前l个元素对应的下标，然后遍历到下标为i的元素时，我们可以从队列q中弹出所有下标小于i-l假设此时队列q中的元素下标分别为$t_1,t_2,\\cdots,t_k$，那么这些下标对应的元素值是依次递减的，也就是说$a_{t_1}>a_{t_2}>\\cdots>a_{t_k}$。那么对于以i结尾的长度为l的区间来说，它的最小值就是at在更新完最小权值之后，我们需要将i加入到队列q中，同时需要保证队列里面的元素下标对应的元素值依然递减。因此，我们在将i加入队列q之前，需要从队列的末尾向前扫描，将所有大于等于ai最后，我们只需要遍历整个数组a，就可以得到所有长度为l的区间中，权值最小的区间的权值了。4.代码实现下面是Python代码的实现：defminInterval(a,l):

n=len(a)

q,ans=[],float('inf')

foriinrange(l):

whileqanda[q[-1]]>=a[i]:

q.pop()

q.append(i)

ans=min(ans,a[q[-1]])

foriinrange(l,n):

whileqandq[0]<i-l+1:

q.pop(0)

whileqanda[q[-1]]>=a[i]:

q.pop()

q.append(i)

ans=min(ans,a[q[-1]])

returnans5.总结本文主要介

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论