ST表（转载自其它博主）

╰半夏微凉° 2024-03-26 23:12 69阅读 0赞

#### 文章目录 ####

*  一、简介
 *  二、Leetcode题目补充
 *   *  1. 2023/9/6 更新

## 一、简介 ##

ST表：[https://zhuanlan.zhihu.com/p/123360481][https_zhuanlan.zhihu.com_p_123360481]

## 二、Leetcode题目补充 ##

### 1. 2023/9/6 更新 ###

`239. 滑动窗口最大值`  
![在这里插入图片描述][07ea2374618a4c2298520957dc4ae7b9.png]

class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            //记录数组的长度
            int length=nums.length;
            //创建返回结果的数组
            int[] cons=new int[length-k+1];
            //确定ST表的跳跃指数
            int j=0;
            while((1<<j)<k){
        
                j++;
            }
             if(j==0)
            {
        
                j++;
            }
            //定义ST数组
            int[][] f=new int[length][j];
            int m1=0;
            //初始化ST数组
            for(int i=0;i<length;i++){
        
                //以i为起点，长度为2的0次方为长度的区间的最大值
                f[i][m1]=nums[i];
            }
            //预处理ST数组
            for(int h=1;h<j;h++){
        
                for(int i=0;i+(1<<h)-1<length;i++){
        
                    f[i][h]=Math.max(f[i][h-1],f[i+(1<<(h-1))][h-1]);
                }
            }
            j--;
            for(int i=0;i<length-k+1;i++){
        
                int m=Math.max(f[i][j],f[i+k-(1<<j)][j]);
                cons[i]=m;
            }
            return cons;
        }
    }

[https_zhuanlan.zhihu.com_p_123360481]: https://zhuanlan.zhihu.com/p/123360481
[07ea2374618a4c2298520957dc4ae7b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/11/9be3103860c64f948edab48661edac29.png

发表评论取消回复

表情：

评论列表（有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读

相关 ST表

ST表什么是ST表 ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到 $ O (n \\log n) ...

谁践踏了优雅/ 2024年04月20日 10:34/ 0 赞/ 55 阅读

相关 ST表（转载自其它博主）

文章目录一、简介二、Leetcode题目补充 1. 2023/9/6 更新一、简介 ST表：[https://zhuanlan.zh

╰半夏微凉°/ 2024年03月26日 23:12/ 0 赞/ 70 阅读

相关【博主的微博】

还没太弄明白微博的价值观，但是感觉至少可以做博客通知，如果您喜欢博主的博文，又想在走路/坐车/排队的时候看，请关注博主的新浪微博：火星人陈勇

我会带着你远行/ 2023年08月17日 15:53/ 0 赞/ 121 阅读

相关【模版】Sparse-Table｜ST表｜基于ST表的RMQ

文章目录 Sparse Table（ST表）详细介绍模版(最小值版本) -------------------- Sparse Table（S

﹏ヽ暗。殇╰゛Y/ 2022年12月28日 12:46/ 0 赞/ 148 阅读

相关博客转载

如何转载别人的博客？下面进行介绍 1.首先找到一篇你想要转载的博客，鼠标右键，选择检查并点击 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW

今天药忘吃喽~/ 2022年11月11日 13:19/ 0 赞/ 242 阅读

相关什么是 web 框架？（转载自博客园）

原文地址：http://www.cnblogs.com/hazir/p/what\_is\_web\_framework.html 博主：[haz

快来打我*/ 2022年08月09日 01:48/ 0 赞/ 186 阅读

相关博客转载

对于喜欢逛CSDN的人来说，看别人的博客确实能够对自己有不小的提高，有时候看到特别好的博客想转载下载，但是不能一个字一个字的敲了，这时候我们就想快速转载别人的博客，把别人的博

布满荆棘的人生/ 2022年06月17日 20:16/ 0 赞/ 204 阅读

相关 ST表

转载博主:[点这里][Link 1] ST表学习作用：ST算法是用来求解给定区间RMQ的最值，本文以最小值为例举例：给出一数组A\[0~5\] = \{5,4

￡神魔★判官ぃ/ 2022年05月28日 07:25/ 0 赞/ 204 阅读

相关其它操作EDM的方式（转载）

通过EdmGen更灵活的控制EDM 在.NET Framework 3.5的文件夹下有一个名为EdmGen的工具，Visual Studio的实体设计器就是调用这个工具来完成

末蓝、/ 2021年12月22日 15:40/ 0 赞/ 162 阅读

相关 ST表模板

普通存最大值，最小值 int a[maxn]; ll Max[MAXN][21]; ll Query(int l,int r) {

梦里梦外;/ 2021年09月19日 05:40/ 0 赞/ 248 阅读