给定一行共 n 人,每人有能力值 a[i]。对所有连续长度为 x 的小组,该组能力值定义为组内最小值;题目要求对所有 1≤x≤n,输出“长度为 x 的所有小组能力值中的最大值”。
核心做法是用 单调栈 预处理每个元素作为“组内最小值”时所能覆盖的最大窗口长度:
对每个位置 i,找到
pre[i]:i 左侧 第一个严格更小 的位置(值 < a[i]),不存在记为 -1;我们可能听过“短板效应”这一说法:一只水桶能盛多少水,并不取决于最长的那块木板,而是取决于最短的那块木板。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册