力扣日练-day4

1、每日温度

  关键：需要返回与原数组等长的数组结果而且双层循环会超时，采用栈结构（存储下标计算天数），用第一个元素的下标初始化栈，构造一个和原数组等长的全0数组表示初始天数，之后遍历原温度数组并更新栈顶元素（若当前温度较高则弹出栈顶元素并计算，将当前元素下标入栈，否则直接将当前元素入栈。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        r=[0 for i in range(len(temperatures))]
        stack=[0]
        for i in range(1,len(temperature)):
            while stack and temperature[i]>stack[-1]:
                j=stack.pop()
                r[j]=i-j
            stack.append(i)
        return r

2、最短无序连续子数组

  关键：若只想通过则可以对原数组排序，将原数组和排序后数组比较即可

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        nums2=sorted(nums)
        left,right=0,len(nums)-1
        while left<len(nums):
            if nums[left]!=nums2[left]:
                break
            left+=1
        if left==len(nums):
            return 0
        while left<right:
            if nums[right]!=nums2[right]:
                break
            right-=1
        return right-left+1

3、将二叉搜索树转化为累加树

  关键：二叉搜索树的中序遍历

class Solution:
    def __init__(self):
        self.sum=0
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:   #递归出口
            return     
        self.convertBST(root.right)
        self.sum+=root.val
        root.val=slef.sum
        self.convertBST(root.left)
        return root