Golang | Leetcode Golang题解之第363题矩形区域不超过K的最大数值和

2024-08-22 07:36

本文主要是介绍Golang | Leetcode Golang题解之第363题矩形区域不超过K的最大数值和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

题解:

import "math/rand"type node struct {ch       [2]*nodepriority intval      int
}func (o *node) cmp(b int) int {switch {case b < o.val:return 0case b > o.val:return 1default:return -1}
}func (o *node) rotate(d int) *node {x := o.ch[d^1]o.ch[d^1] = x.ch[d]x.ch[d] = oreturn x
}type treap struct {root *node
}func (t *treap) _put(o *node, val int) *node {if o == nil {return &node{priority: rand.Int(), val: val}}if d := o.cmp(val); d >= 0 {o.ch[d] = t._put(o.ch[d], val)if o.ch[d].priority > o.priority {o = o.rotate(d ^ 1)}}return o
}func (t *treap) put(val int) {t.root = t._put(t.root, val)
}func (t *treap) lowerBound(val int) (lb *node) {for o := t.root; o != nil; {switch c := o.cmp(val); {case c == 0:lb = oo = o.ch[0]case c > 0:o = o.ch[1]default:return o}}return
}func maxSumSubmatrix(matrix [][]int, k int) int {ans := math.MinInt64for i := range matrix { // 枚举上边界sum := make([]int, len(matrix[0]))for _, row := range matrix[i:] { // 枚举下边界for c, v := range row {sum[c] += v // 更新每列的元素和}t := &treap{}t.put(0)s := 0for _, v := range sum {s += vif lb := t.lowerBound(s - k); lb != nil {ans = max(ans, s-lb.val)}t.put(s)}}}return ans
}func max(a, b int) int {if a > b {return a}return b
}

这篇关于Golang | Leetcode Golang题解之第363题矩形区域不超过K的最大数值和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1095639

相关文章

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性

Golang中map缩容的实现

《Golang中map缩容的实现》本文主要介绍了Go语言中map的扩缩容机制,包括grow和hashGrow方法的处理,具有一定的参考价值,感兴趣的可以了解一下... 目录基本分析带来的隐患为什么不支持缩容基本分析在 Go 底层源码 src/runtime/map.go 中,扩缩容的处理方法是 grow

golang获取prometheus数据(prometheus/client_golang包)

《golang获取prometheus数据(prometheus/client_golang包)》本文主要介绍了使用Go语言的prometheus/client_golang包来获取Prometheu... 目录1. 创建链接1.1 语法1.2 完整示例2. 简单查询2.1 语法2.2 完整示例3. 范围值

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

golang内存对齐的项目实践

《golang内存对齐的项目实践》本文主要介绍了golang内存对齐的项目实践,内存对齐不仅有助于提高内存访问效率,还确保了与硬件接口的兼容性,是Go语言编程中不可忽视的重要优化手段,下面就来介绍一下... 目录一、结构体中的字段顺序与内存对齐二、内存对齐的原理与规则三、调整结构体字段顺序优化内存对齐四、内

Golang操作DuckDB实战案例分享

《Golang操作DuckDB实战案例分享》DuckDB是一个嵌入式SQL数据库引擎,它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的,DuckDB支持各种数据类型和SQL特性... 目录DuckDB的主要优点环境准备初始化表和数据查询单行或多行错误处理和事务完整代码最后总结Duck