1000ms

Difficulty: 3

所属公司 : 华为

时间 :2023年9月27日-国内-非AI方向

算法与标签>栈

会员或题库专享

请先，开通会员或购买题库华为校招机考题库，可解锁完整内容。

购买华为校招机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（华为校招机考题库），可解锁完整内容。

购买题库开通会员

向左扫描朴素解法

这道题的正解是 $单调栈$ ，但是我们用朴素解法 $向左暴力扫描$ 也能在考试时拿到一定的分数。

题意：对每个下标 $i$ ，它的美好值是左边最近的、满足 $a[j]\le a[i]$ 的 $a[j]$ ；若没有则为 $0$ 。求所有位置美好值之和。

朴素做法：对每个 $i$ ，从 $i-1$ 往左扫，遇到第一个 $\le a[i]$ 的数就停下，把它累加到答案里。

$n$ 较小时 $O(n^2)$ 可通过；当 $n$ 接近 $10^5$ 时会超时，需要后面的单调栈做法。