数据规模比较大，算法必须是O(n)的。
可以预先使用O(n)时间计算nums[0] .. nums[i]的最大值，存在left[i]中，以及nums[i] .. nums[n-1]的最小值存在right[i]中。然后再按题目的定义计算即可。
时间复杂度：O(n)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int sumOfBeauties(vector<int>& nums) { const int n = nums.size(); vector<int> left(n, nums[0]); vector<int> right(n, nums.back()); for (int i = 1; i < n; ++i) left[i] = max(left[i - 1], nums[i]); for (int i = n - 2; i >= 0; --i) right[i] = min(right[i + 1], nums[i]); int ans = 0; for (int i = 1; i < n - 1; ++i) if (left[i - 1] < nums[i] && nums[i] < right[i + 1]) ans += 2; else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) ans += 1; return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment