I 吊打 std

EgLund · 2021-08-31 16:39:17 · 个人记录

一个长度为 n ，每个元素算作一个长度为 1 的窗口，2 个连在一起的元素算作一个长度为 2 个窗口，以此类推。

长度为 1 的窗口共有 n 个，长度为 2 的窗口共有 n-1 个，……长度为 n 的窗口共有 1 个。

每个窗口的值是其包含元素的最小值。

给出一个长度为 n 的数组，分别输出长度为 1 \to n 的窗口中的最大值。

例如：4 1 5 8 7

长度为 1 的窗口为 4/1/5/8/7 => 值为 4 1 5 8 7，其最大值为 8。

长度为 2 的窗口为 4 1/1 5/5 8/8 7 => 值为 1 1 5 7，最大值为 7。

长度为 3 的窗口为 4 1 5/1 5 8/5 8 7 => 值为 1 1 5，最大值为 5。

长度为 4 的窗口为 4 1 5 8/1 5 8 7 => 值为 1 1，最大值为 1。

长度为 5 的窗口为 4 1 5 8 7 => 值为 1，最大值为 1。

std 是 \mathcal O(n \log n) 的，复杂度瓶颈在排序。

给一个 \mathcal O(n) 的无需排序的解法。

我们用单调栈求出每个数作为最小值的范围。

例如 4 2 3 5 1 8 中，数字 5 作为最小值的范围是 [4,4]，而数字 2 的范围是 [1,4]。

然后我们记录范围 长度 为 i 的最大 元素值 val_i。

我们从大往小扫描 val 数组，记录 \max \limits _{i=u}^{n}val_i = ans_u。