202. Segment Tree Query
2024-08-30 16:14:42
最后更新
二刷
09-Jan-17
正儿八经线段树的应用了。 查找区间内的值。
对于某一个Node,有这样的可能:
1)需要查找区间和当前NODE没有覆盖部分,那么直接回去就行了。
2)有覆盖的部分,覆盖部分作为新的查找区间,往左右子找。
Time: O(NlgN)
Space: O(lgN) for memory stack
public class Solution {
public int query(SegmentTreeNode root, int start, int end) {
if (root == null) return Integer.MIN_VALUE;
if (end < root.start || start > root.end) return Integer.MIN_VALUE;
int newStart = Math.max(root.start, start);
int newEnd = Math.min(root.end, end);
if (newStart == root.start && newEnd == root.end) return root.max;
return Math.max(query(root.left, newStart, newEnd),
query(root.right, newStart, newEnd));
}
}
最新文章
- 关于lr调用jar在vuser中可以运行,但是controller中却报错的问题
- Codeforces Alpha Round #20 (Codeforces format) C. Dijkstra?(裸的dijkstra)
- [C] zlstdint(让VC、TC等编译器自动兼容C99的整数类型)V1.0。支持Turbo C++ 3等DOS下的编译器
- Linux 配置网络
- Mysql笔记——触发器简单实例
- 题解西电OJ (Problem 1005 -跳舞毯)--动态规划
- 学习Visitor Pattern 有感而发!override and overload
- python进阶八_警告和异常
- [转]Iphone m3u8 segmenter from ffmpeg for video streaming
- Vue中table表头合并的用法
- ubuntu通过apt-get安装JDK8
- 【C++ STL】Set和Multiset
- mysql设置指定ip访问,用户权限相关操作
- Spring Boot 揭秘与实战(二) 数据存储篇 - ElasticSearch
- 第7章 Iptables与Firewalld防火墙。
- [golang note] 包和导入
- spring集成spring mvc 和hibernate详解
- Python-RabbitMQ消息队列的发布与订阅
- 面试问题 - C# 接口和抽象类的区别
- pandas模块(很详细归类),pd.concat(后续补充)
热门文章
- python3 进程与线程
- Open Cascade:如何从AIS_Shape导出TopoDS_Shape?
- AspNetCore容器化(Docker)部署(二) —— 多容器通信
- Java编程:常见问题汇总
- C++ new delete(一)
- 读懂CommonJS的模块加载
- 35个Redis面试题
- 微信小程序的坑之wx.miniProgram.postMessage
- 第十三章:MFC库与Windows程序开发概述
- 周三面试Python开发,这几道Python面试题差点答错,Python面试题No7