区间求最值问题高效解决方法

对于区间求最值场景，如果区间不定长度的，可以使用稀疏表进行求解，如果区间是固定长度的，则可以使用分块的思想（与稀疏表原理类似），都是通过压缩状态个数，

1 关于稀疏表的原理详见：

稀疏表（Sparse Table，ST原理及应用场景
下面是一个稀疏表的python实现

class Solution:
    def __init__(self, nums):
        self.nums = nums
        self.init_value = -9999999999999
        self.st = self.initSparseTable(self.nums)


    def initSparseTable(self, nums):
        # 初始化稀疏表
        self.init_value = -9999999999999
        steps = math.floor(math.log(len(self.nums), 2))
        st = [[self.init_value for _ in range(steps + 1)] for _ in range(len(self.nums))]
        for i in range(len(self.nums)):
            k = math.floor(math.log(len(self.nums) - i, 2))
            for j in range(k):
                st[i][j] = self.sparseTable(st, i, j)
        return st

    def sparseTable(self, st, i, j):
        if j == 0:
            return self.nums[i]

        if st[i][j] != self.init_value:
            return st[i][j]
        else:
            tmp_max = max(self.sparseTable(st, i, j - 1), self.sparseTable(st, int(i + math.pow(2, j - 1)), j - 1),)
            st[i][j] = tmp_max
            return tmp_max

    def maxSlidingWindow(self, nums: list, k: int) -> list[int]:
        # 求所有k个区间的最值
        l1 = []
        j = int(math.floor(math.log(k, 2)))

        if int(math.pow(2, j)) == k:
            for i in range(0, len(nums) - k + 1):
                l1.append(self.st[i][j])
        else:
            for i in range(0, len(nums) - k + 1):
                l1.append(max(self.st[i][j], self.st[i + k - int(math.pow(2, j))][j]))

        return l1

通过分块求固定区间长度最值

1，首先将数组nums按照区间的长度k从左到右依次分为若干个长度均为k的小块

2 申请两个数组，preMax[i]，postMax[i] {i 为数组的下标}；preMax[i]表示在nums[i]元素所在的分块内作为最后一个元素的前缀最大值，postMax[i]表示在nums[i]元素所在的分块内作为第一个元素的后缀最大值
如下图所示，假设区间长度=3，数组nums = [1,3,-1,-3,5,3,6,7]，i=3时，preMax[3] 表示在块2 i=3作为前缀最后一个元素的前缀最大值，很明显就nums[3]一个元素，就是nums[3]，

通过一次正序遍历nums数组可以得到preMax数组
通过一次倒序遍历nums数组可以得到postMax数组

3 根据得到的postMax，preMax数组，可以快速求出任何一个区间[i， i + k - 1]中最值，这里有两个种情况，当i为k的整倍数或者不为k的整数倍

• i为k的整数倍
  直接通过postMax[i]获取结果

• 当i不为k的整数倍，那么[i， i + k - 1]一定时跨了两个小块，假设为[i，j - 1],[j， i + k - 1]，其中j为后面那个小块的首位 元素，则可以取postMax[i]与preMax[ i + k - 1]的最大值作为结果
  下面为python代码的实现，用来求数组中所有区间为 k的最大值

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        # 分块思想
        preSum = [0] * len(nums)
        postSum = [0] * len(nums)
        for i in range(len(nums)):
            if i % k == 0:
                curr_max = nums[i]
            curr_max = max(curr_max, nums[i])
            preSum[i] = curr_max

        curr_max = nums[-1]
        for i in range(len(nums) - 1, -1, -1):
            if i % k == (k - 1):
                curr_max = nums[i]
            curr_max = max(curr_max, nums[i])
            postSum[i] = curr_max
        l1 = []
        for i in range(len(nums) - k + 1):
            if i % k == 0:
                l1.append(postSum[i])
            else:
                l1.append(max(postSum[i], preSum[i + k - 1]))
        return l1