Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给一列数,若其中第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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理