【数据结构与算法面试宝典】16 如何利用 DP 与单调队列寻找最大矩形？
(持续更新中，欢迎关注！)
文章目录
- 【数据结构与算法面试宝典】16 如何利用 DP 与单调队列寻找最大矩形？
- 最大矩形
- 暴力算法
- 特点 1：区间
- ST 算法
- 1\. 一分为二
- 2\. 指数表示法
- 线段树
- 1\. 线段树的思想
- 2\. 查询的本质
- 3\. 线段树的更新
- 4\. 线段树的存储
- 5\. 线段树的模板代码
- 特点 2：选与不选
- 分治算法 1
- 分治算法 2
- 特点 3：左右两边较小的数
- 小于我的位置
- 单调栈的性质
- DP
- 总结
- 思考题
面试的场景与之前学习某个知识点的情况不再相同。在学习“一解多题”的时候，由于已经预设了前提，实际上是知道某个题会用到什么知识点的。
但是在面试中，当你拿到一个题目，可能一时想不到具体采用哪种解法。所以在本讲，我将带你回到面试场景，教你分析题目的思路。的目标就变成从题目出发，去考虑如何破解一个题。
本讲将会重点学习：
如何挖掘题目的特点
如何利用特点匹配到数据结构和算法知识点
完成这两步动作，需要你熟练地掌握前面“一解多题”模块介绍的数据结构与算法知识点。养兵千日，用在一时，是时候派上用场了。
最大矩形
【题目】给定一个数组，里面有n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：[2,1,5,6,2,3]
输出：10
解释：柱状图的示例，其中每个柱子的宽度为 1，给定的高度为[2,1,5,6,2,3]。
输入 最大矩形
暴力算法
当拿到题目之后，一种最简单、最暴力的算
