ST算法求解RMQ问题的模板

谁借莪１个温暖的怀抱￠ 2022-08-29 09:57 127阅读 0赞

**ST算法**主要用来快速求解某个区间的最大/小值问题（RMQ问题），需要借助于一个二维数组dp进行预处理，预处理的时间复杂度为O(nlogn)，预处理的过程主要使用了倍增的思想，查询的时间复杂度为O(1)，所以整个算法时间复杂度为O(nlogn)。我们需要声明一个二维数组，其中第一维的长度为n，第二维的长度为k + 1，其中n为数组的长度，k = log2n，dp\[i\]\[j\]表示区间\[i，i + 2 ^ j - 1\]的最值，递推的时候以2 ^ (j - 1)作为分隔点分为左右两部分求解最值，所以dp的状态转移方程为dp\[i\]\[j\] = max\{dp\[i\]\[j - 1\]，dp\[i + 2 ^ (j - 1)\]\[j - 1\]\}，我们可以使用两层循环进行状态计算，第一层循环表示区间的某个起点i开始的长度为j，第二层循环表示区间的起点i，为什么第一层循环先是某个起点开始的长度呢？这是由dp数组的状态转移方程决定的，我们在状态转移的时候当前状态的值依赖于上一个状态的值，所以需要先计算出j - 1的状态那么才可以计算出当前状态j，所以最外层的循环为某个区间起点对应的长度j，预处理的时间复杂度为O(nlogn)，查询区间最值的时间复杂度为O(1)，所以整个算法的时间复杂度为O（nlogn）。在查询区间\[l， r\]最值的时候那么我们直接使用公式查询即可： a = dp\[l\]\[k\]，b = dp\[r - (1 << k) + 1\]\[k\]，其实也是以k = logn作为分隔点求解以分隔点k的左右两部分的最值即可，为什么使用分为两个部分来求解最值呢？因为只有两个部分同时求解最值才可以覆盖当前的区间的所有数字这样求解的最值才是正确的。我们可以理解其中的思路记住代码，考试的时候直接写出来即可。

import random
    from typing import List
    import math
    
    
    class Solution:
        def get(self, nums: List[int]):
            n = len(nums)
            k = int(math.log(n, 2))
            dp = [[0] * (k + 1) for i in range(n)]
            for j in range(k + 1):
                i = 0
                while i + (1 << j) - 1 < n:
                    # 当j为0的时候那么为当前位置的值
                    if j == 0:
                        dp[i][j] = nums[i]
                    # 在状态转移的时候需要知道上一个j-1的状态所以最外层的循环为以起点i的长度j, 当前状态j依赖于上一个状态
                    else:
                        dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1])
                    i += 1
            return dp
    
        def query(self, l: int, r: int, dp: List[List[int]]):
            range_len = r - l + 1
            k = int(math.log(range_len, 2))
            # 以当前的log2n作为分隔点求解左右两边的最值
            return max(dp[l][k], dp[r - (1 << k) + 1][k])
    
    
    if __name__ == '__main__':
        n = 10
        nums = list()
        for i in range(n):
            # 随机生成n个数字
            nums.append(random.randint(1, n * 6))
        # nums为当前的随机数列表
        print(nums)
        dp = Solution().get(nums)
        # 求解区间[l, r]的最大值
        l, r = n - 4, n - 1
        res = Solution().query(l, r, dp)
        print(res)