對于區間求最值場景，如果區間不定長度的，可以使用稀疏表進行求解，如果區間是固定長度的，則可以使用分塊的思想（與稀疏表原理類似），都是通過壓縮狀態個數，
1 關于稀疏表的原理詳見：
稀疏表（Sparse Table，ST原理及應用場景
下面是一個稀疏表的python實現
class Solution:def __init__(self, nums):self.nums = numsself.init_value = -9999999999999self.st = self.initSparseTable(self.nums)def initSparseTable(self, nums):# 初始化稀疏表self.init_value = -9999999999999steps = 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 stdef 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_maxreturn tmp_maxdef 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_maxcurr_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_maxl1 = []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
)
