单调栈 看完此篇：去练下手吧！https://leetcode-cn.com/problems/largest-rectangle-in-histogram/ 最常见题型：给定一个数组，找出数组中每个数左边 / 右边比其小且离它最近的数的位置 优化其实在于：对于数组中的某些数，如果 存在 Ax >= Ak，且 Ax在 Ak的右边，那么 Ax就永远不会被用到 因此，当存在这种关系时，可以去将 Ax删除掉，即此时便形成了一个 单调栈 (递增) 基本思想：构建单调栈，每次循环时加入当前数组下标，因为 要将当前数入栈…

归并 看完此篇，练手：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/，但注意一点：当数组长度 > 100000，最坏情况下是超出 Integer.MAX_VALUE，此时便需要 long来存. 同样是 分治思想，区别于快排 先递归进行排序，再进行合并 基本思想： 确定分界点：mid = l + r >> 1 递归排序，区间划分，即对子区间先进行排序 -> 此步结束后实际上已经是有序的两个区间的了 归并有序区间 …

快排 看完此篇，你便可以去来练下手：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/submissions/ 基本思想：采用 分治 确定一个边界：q[l]，q[ l + r >> 1]，q[r] 调整范围：边界左边小于等于边界，边界右边大于等于边界 -> 左区间的最大值小于等于右区间的最小值 如何优雅来进行范围的调整？ 可以采用 双指针做法，这也避免了额外空间，同样是线性扫描 每次循环，左右指针先进行移位后，再来进行逻辑判断 递归…

二分 看完本篇文章，你就可以去练一下手：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/，https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/ 整数二分 有 单调性肯定可以进行二分，但是可以进行二分的不一定是有单调性的 二分本质上就是可以通过定义一个 性质(二段性)，将一个区间划分为两个不…

子串 一个字符串有多少个子串？ 对一个长为 n的字符串，子串数量怎么来计算？ 对于长为为 1的子串，有 n种 对于长为为 2的子串，有 n - 1种 .... 对于长为为 n的子串，有 1种 发现了什么？这不就是等差数列吗！d = 1，a1 = n，an = 1 再加上空串的份，总子串数量便是 (a1 + an)nd/ 2 + 1 = (1 + n)n / 2 + 1，及约等于 n^2 / 2 知道了子串数量后，那怎么来枚举所有的子串？ 暴力枚举显然不可取，任何时候，应当先去考虑 时间复杂度(最为紧张)，空间复杂度…

队列 队列是一个有序列表，可以用数组或链表来实现 基于数组来模拟队列 对头front，随数据输出而改变 对尾rear，随数据的输入而改变 实现思路 存入一个数据 将尾指针rear往后移，当front == rear 时，队列为空 如果尾部指针rear 小于队列的最大下标 maxSize-1,则将数据存入rear所指的数组元素中，否则将无法存入数据 代码实现 public class ArrayQueueDemo { public static void main(String[] args) { ArrayQueu…

非线性结构 数据元素之间不一定都是一一对应的关系 二维数组 可以用矩阵来表示，两个或者多个下标值对应一个值，是多对一的关系，虽然实际存储时仍然是顺序存储的，但从逻辑上来讲已经不是线性结构了 稀疏数组 SparseArray 实际应用需求 编写五子棋程序中，有存盘退出和续上盘的功能 分析问题： 该二维数组中很多值都是默认值0，因此记录了很多没有意义的数据 --> 稀疏数组 稀疏数组实际上对二维数组的进一步压缩 当一个数组中大部分元素为0，或者为同一个值的元素时，可以使用稀疏数组来保存该数组 稀疏数组实际上是行数…