leetcode-2846、560、239、76

题目链接

2846. 边权重均等查询 - 力扣（LeetCode）

解题思路

LCA看不懂

算法详解之最近公共祖先(LCA) - hulean - 博客园 (cnblogs.com)

leetcode-hot100

和为K的子数组

题目链接

560. 和为 K 的子数组 - 力扣（LeetCode）

解题思路

1、暴力破解

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        result = 0
        for i in range(n):
            for j in range(i, n):
                temp = nums[i:j+1]
                #print(temp)
                sum_ = sum(temp)
                if sum_ == k:
                    result += 1
        return result

超出时间限制

加入改进通过使用一个数组记录前n个数的和，降低时间复杂度。

滑动窗口最大值

题目链接

239. 滑动窗口最大值 - 力扣（LeetCode）

暴力破解

超出时间限制

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        left = 0
        right = k - 1
        n = len(nums)
        result = []
        while right < n:
            minstr = nums[left:right+ 1]
            result.append(max(minstr))
            right += 1
            left += 1
        return result

优先队列：

对于最大值，我们可以想到一种非常合适的数据结构，那就是优先队列，其中的大根堆可以帮助我们实时维护一系列元素的最大值。

对于本题而言，初始时，我们将数组nums的前k个元素放入优先队列中。每当我们向右移动窗口时，我们就把一个新的元素放入优先队列中。此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组nums中的位置出现在滑动窗口左边界的左侧1.因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中，我们可以将其永久的从优先队列中移除。

我们不断移除堆定的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组，表示元素num在数组中的下标位index。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        #注意python默认的优先队列时小根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k,n):
            heapq.heappush(q,(-nums[i],i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans