Posted on 2022-11-11 18:52
Uriel 閱讀(56)
評論(0) 編輯 收藏 引用 所屬分類:
閑來無事重切Leet Code 、
大水題
給一列數(shù)，若其中第i個數(shù)滿足：
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的數(shù)字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