学习笔记

五毒神掌 最大的误区 刷题只刷一遍 核心思想 升维 空间换时间 跳表 只能用于元素有序的情况 对标的是平衡二叉树和二分查找 时间复杂度 插入/删除/搜索o(log n) 空间复杂度 o(n)【内存会有一个浪费，因为需要存储索引】 原理简单、容易实现、方便扩展、效率更高 如何给有序的链表加速 一般的加速是升维，比如一维升二维 双指针法 有序的数组

移动零 单指针指向最后不是0的元素的下标 盛最多水的容器 双指针，一个指向开始一个指向结尾，夹逼的方法往中间移动(每次找到两个数的最小值) 3数之和 排序 满足 a+b=c 一层循环加前后指针 有两个地方需要注意： 一是在外层循环中需要判断重复项并跳过和需要 c 是小于0的(因为如果当前c已经大于0 那么之后的数肯定也是大于0的) 二是内层 while 循环 判断如果等于 0 那么前后指针就需要跳过相等数的 判断一个整数是否是回文数(不转字符串) 通过 $n % 10 找到最后的个位数

优先队列 插入操作 o(1) 去除操作 o(logN)-按照元素的优先级取出 底层具体实现的数据结构较为多样和复杂：heap(堆)、bst(二叉搜索树)、treap 堆 最大堆 最小堆 golang container/heap 堆 是一个完全二叉树 (叶子节点不满，那就从左插入) 本身是继承 sort 排序的 所以要实现需要继承5个接口 push/pop/Less/Swap/Len 本身是通过切片来维护 主要实现有 pop->down(下沉：将当前元素(i)与它的两个子节点(2i+1，2i+2)进行比较如果大于就交换)和push->up(上升：将当前元素(i)与它的父节点((j - 1) / 2)进行比较如果小于就交换)

最近相关性-栈 先来后到-队列

有效括号 最小栈