当前位置：首页 > news >正文

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

news 2025/6/26 17:00:21

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

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