Posted on 2022-11-11 18:52
Uriel 阅读(28)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
大水题
给一列数，若其中第i个数满足：
nums[j] < nums[i] < nums[k], for all 0 <= j < i and for all i < k <= nums.length - 1，那么beauty值为2
否则如果满足 nums[i - 1] < nums[i] < nums[i + 1]，那么beauty值为1
其他情况beauty值为0
判断beauty值为2的方法：
预处理两个list，dmax[i]记录从第0位到第i位置的最大值，dmin[i]记录从最后一位前推到第i位的最小值，如果某一位i的数字nums[i]满足dmax[i - 1] < nums[i] and nums[i] < dmin[i + 1]，那么该位的beauty值为2
判断beauty值为1的判断就直接对比nums[i-1]和nums[i+1]就行
1 #2012
2 #Runtime: 1113 ms
3 #Memory Usage: 26 MB
4
5 class Solution(object):
6 def sumOfBeauties(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 dmax = [nums[0]] * len(nums)
12 dmin = [nums[-1]] * len(nums)
13 for i in range(1, len(nums)):
14 dmax[i] = max(dmax[i - 1], nums[i])
15 for i in range(len(nums) - 2, -1, -1):
16 dmin[i] = min(dmin[i + 1], nums[i])
17 ans = 0
18 for i in range(1, len(nums) - 1):
19 if dmax[i - 1] < nums[i] and nums[i] < dmin[i + 1]:
20 ans += 2
21 elif nums[i - 1] < nums[i] and nums[i] < nums[i + 1]:
22 ans += 1
23 return ans