- 一级目录
- 二级目录
- 三级目录）
- 数据结构
- 1.算法性能分析
- 1.1 时间复杂度
- 1.2 递归算法的时间复杂度
- 1.3 空间复杂度
- 2. 栈和队列
- 2.1 栈
- 数据结构
- 1.算法性能分析
- 1.1 时间复杂度
- 1.2 递归算法的时间复杂度
- 1.3 空间复杂度
- 2. 栈和队列
- 2.1 栈
- 2.1.1 底层实现原理
- 2.1.2 括号匹配问题
- 2.1.3 删除字符串中的所有相邻重复项
- 2.1.4 逆波兰表达式求值
- 2.1.5 最小栈
- 2.1.6 单调栈（未完待续）
- 2.2 队列
- 2.2.1 底层原理
- 2.2.2单调队列
- 2.2.3 优先队列（未完）
- 2.2.4 双端队列(未完)
- 2.3 用栈实现队列
- 2.4 用队列实现栈
1. 时间复杂度（大O）：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。 2. 在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项等等），要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适（在有常数项的时候）。 3. 我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示： O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶 大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。1.2 递归算法的时间复杂度
1. 递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。
2. 要根据具体的 情况来看，来逐步分析递归算法的时间复杂度，注意不要一看到递归就想到了O(logn)。
3. 递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度
** 算法题：求x的n次方
int function1(int x, int n) {
int result = 1; // 注意 任何数的0次方等于1
for (int i = 0; i < n; i++) {
result = result * x;
}
return result;
}
*复杂度为O（N)
int function3(int x, int n) {
if (n == 0) {
return 1;
}
if (n % 2 == 1) {
return function3(x, n / 2) * function3(x, n / 2)*x;
}
return function3(x, n / 2) * function3(x, n / 2);
}
* 复杂度为O（n),而不是O（logn)
int function4(int x, int n) {
if (n == 0) {
return 1;
}
int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
if (n % 2 == 1) {
return t * t * x;
}
return t * t;
}
复杂度为O（logn)1.3 空间复杂度
1. 空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。2. 栈和队列 2.1 栈
1. Push操作：分为栈的数组实现和栈的链表实现
栈的数组实现：
栈的链表实现：
2. pop操作：
栈的数组实现：
栈的链表实现：
4. peek操作：
1. 时间复杂度（大O）：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。
2. 在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项等等），要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适（在有常数项的时候）。
3. 我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示：
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶
大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。
1.2 递归算法的时间复杂度
1. 递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度。 2. 要根据具体的情况来看，来逐步分析递归算法的时间复杂度，注意不要一看到递归就想到了O(logn)。 3. 递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深 度 4. 编程语言的一些功能实现也会使用栈结构，实现函数递归调用就需要栈，但不是每种编程语言都支持递归。递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
** 算法题：求x的n次方
int function1(int x, int n) {
int result = 1; // 注意 任何数的0次方等于1
for (int i = 0; i < n; i++) {
result = result * x;
}
return result;
}
- 复杂度为O（N)
int function3(int x, int n) {
if (n == 0) {
return 1;
}
if (n % 2 == 1) {
return function3(x, n / 2) * function3(x, n / 2)*x;
}
return function3(x, n / 2) * function3(x, n / 2);
}
- 复杂度为O（n),而不是O（logn)
int function4(int x, int n) {
if (n == 0) {
return 1;
}
int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
if (n % 2 == 1) {
return t * t * x;
}
return t * t;
}
- 复杂度为O（logn)
1. 空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。2. 栈和队列 2.1 栈
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。 栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。2.1.1 底层实现原理
要先注意栈顶指针指向当前元素还是当前元素的下一个元素。
- Push操作：分为栈的数组实现和栈的链表实现
栈的数组实现：
栈的链表实现：
2. pop操作：
栈的数组实现：
栈的链表实现：
3. peek操作：
- Java中有专门的接口和类实现了栈的原理。Deque接口，数组栈用ArrayDeque，链表栈用LinkedList。
2.1.2 括号匹配问题
- 算法题：
题目描述：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。链接：https://leetcode.cn/problems/valid-parentheses
- 思路1：括号匹配是典型的使用栈来解决的问题。我们从左往右遍历，每当遇到左括号便放入栈内， 遇到右括号则判断其和栈顶的括号是否是统一类型，是则从栈内取出左括号，否则说明字符串不 合法。
- 思路2：在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单。
Deque<> stack = new ArrayDeque<>(); E pop() 从此列表表示的堆栈中弹出一个元素。 void push(E e) 将元素推送到此列表表示的堆栈上。 E peek() 检索但不删除此列表的头部（第一个元素）。
class Solution {
public boolean isValid(String s) {
//1.建立栈
Deque stack = new ArrayDeque();
//2.遍历字符串
char ch;
for (int i = 0; i < s.length(); i++){//这里length()后边的括号一定不要忘记
ch = s.charAt(i);
//3.当遇到左括号时，将对应有括号入栈
if(ch=='('){
stack.push(')');
}else if(ch == '['){
stack.push(']');
}else if(ch == '{'){
stack.push('}');
}else if(stack.isEmpty() || stack.peek() != ch){
//4.遇到右括号时，查询是否和栈顶元素一样，不同返回false；或者此时栈为空也返回false
return false;
}else{
//相同则出栈
stack.pop();
}
}
//5.判断字符串遍历完成后，栈里面是否还有元素
return stack.isEmpty();
}
}
2.1.3 删除字符串中的所有相邻重复项
题目描述：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string
- 思路1：直接暴力解题，用StringBuffer接受字符串，遍历字符串，当StringBuffer为空时，直接将字符加入StringBuffer，当StringBuffer有内容时，加入时要进行比较，如果和已有的StringBuffer的最后一个字符相同，则删除的上一个字符，否则直接加入，最后转为Sring输出。
- 思路2：用栈。本题要删除相邻相同元素，其实也是匹配问题，相同左元素相当于左括号，相同右元素就是相当于右括号，匹配上了就删除。可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。
//第一种
class Solution {
public String removeDuplicates(String s) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < s.length(); i++){
//如果sb为空，则直接加入
if(sb.length() == 0){
sb.append(s.charAt(i));
}else{
//如果不为空，加入时判断是否和sb的上一个字符相同，相同则删去
if(sb.charAt(sb.length()-1) == s.charAt(i)){
sb.deleteCharAt(sb.length()-1);
}else{
//不同则直接加
sb.append(s.charAt(i));
}
}
}
// 打印最终结果
return sb.toString();
}
}
//第二种
class Solution {
public String removeDuplicates(String S) {
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < S.length(); i++) {
ch = S.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
String str = "";
//剩余的元素即为不重复的元素
while (!deque.isEmpty()) {
str = deque.pop() + str;
}
return str;
}
}
//直接拿字符串直接作为栈，省去了栈还要转为字符串的操作。
class Solution {
public String removeDuplicates(String s) {
// 将 res 当做栈
StringBuffer res = new StringBuffer();
// top为 res 的长度
int top = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
if (top >= 0 && res.charAt(top) == c) {
res.deleteCharAt(top);
top--;
// 否则，将该字符 入栈，同时top++
} else {
res.append(c);
top++;
}
}
return res.toString();
}
}
2.1.4 逆波兰表达式求值
题目描述：根据 逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation
- 思路：适合用栈操作运算：遇到数字则入栈，遇到运算符则取出栈顶两个数字进行运算，并将结果压入栈中。
class Solution {
public int evalRPN(String[] tokens) {
Deque dq = new ArrayDeque();
String str ;
for(int i = 0; i < tokens.length; i++){
str = tokens[i];
//遍历到运算符时
if("+".equals(str)){
dq.push(dq.pop() + dq.pop());
}else if("-".equals(str)){
dq.push(-dq.pop() + dq.pop());
}else if ("*".equals(str)){
dq.push(dq.pop() * dq.pop());
}else if("/".equals(str)){
int t1 = dq.pop();
int t2 = dq.pop();
dq.push(t2 / t1);
}else{
//非运算符则直接压入栈
dq.push(Integer.parseInt(str));
}
}
//遍历完成后，输出最终结果
return dq.peek();
}
}
2.1.5 最小栈
题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
链接：https://leetcode.cn/problems/min-stack
- 思路：我们可以额外建立一个新栈，栈顶表示原栈里所有值的最小值。每当在原栈里插入一个数字
时，若该数字小于等于新栈栈顶，则表示这个数字在原栈里是最小值，我们将其同时插入新栈内。
每当从原栈里取出一个数字时，若该数字等于新栈栈顶，则表示这个数是原栈里的最小值之一，
我们同时取出新栈栈顶的值。
一个写起来更简单但是时间复杂度略高的方法是，我们每次插入原栈时，都向新栈插入一次
原栈里所有值的最小值（新栈栈顶和待插入值中小的那一个）；每次从原栈里取出数字时，同样
取出新栈的栈顶。这样可以避免判断，但是每次都要插入和取出。
** 一定要注意 == 和equals 的区别
class MinStack {
Deque dq1;//原栈
Deque dq2;//最小栈
public MinStack() {
dq1 = new LinkedList();
dq2 = new LinkedList();
}
public void push(int val) {
//对原栈，直接压入原栈
dq1.push(val);
//当最小栈为空时，直接将元素压入栈中，若最小栈不为空，则要进行判断
if(dq2.isEmpty()){
dq2.push(val);
}else{
//若当前输入元素小于或等于最小栈的栈顶元素，则加入最小栈中
if(val <= dq2.peek()){//注意：一定要有等于
dq2.push(val);
}//若不小于，则不加入
}
}
public void pop() {
//对于最小栈，若是推出的元素等于栈顶元素，则最小栈也推出栈顶元素
if(dq1.peek().equals(dq2.peek())){
//这里不能用 == ，必须用.equals();
dq2.pop();
}
//原栈则直接出
dq1.pop();
}
public int top() {
//原栈直接获取
return dq1.peek();
}
public int getMin() {
//当最小栈不为空时，直接获取栈顶元素
// if( !dq2.isEmpty())
return dq2.peek();
// }
// //若最小栈为空，输出0
// return 0;
}
}
2.1.6 单调栈（未完待续）
题目描述 ：给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
链接：https://leetcode.cn/problems/daily-temperatures
2.2 队列 2.2.1 底层原理
- 思路：我们可以维持一个单调递减的栈，表示每天的温度；为了方便计算天数差，我们这里存放位
置（即日期）而非温度本身。我们从左向右遍历温度数组，对于每个日期 p，如果 p 的温度比栈
顶存储位置 q 的温度高，则我们取出 q，并记录 q 需要等待的天数为 p − q；我们重复这一过程，
直到 p 的温度小于等于栈顶存储位置的温度（或空栈）时，我们将 p 插入栈顶，然后考虑下一天。
在这个过程中，栈内数组永远保持单调递减，避免了使用排序进行比较。最后若栈内剩余一些日
期，则说明它们之后都没有出现更暖和的日期。
用链表实现
用数组实现
用固定数组实现的形式效率不高，可以考虑用环形数组。
实现过程略。
2.2.2单调队列
- Java中提供了Queue接口，由多个类来实现（包括LinkedList）。Queue接口定义了许多方法。
滑动窗口
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
链接：https://leetcode.cn/problems/sliding-window-maximum
- 思路：设计单调队列的时候，pop，和push操作要保持如下规则：
- pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。
Deque<> dq = new LinkedList<>(); E poll() 检索并删除此列表的头部（第一个元素）。 boolean add(E e) //将指定元素附加到此列表的末尾。 void addFirst(E e) 在此列表的开头插入指定元素。 void addLast(E e) 将指定元素附加到此列表的末尾。 E peek() 检索但不删除此列表的头部（第一个元素）。 E remove() 检索并删除此列表的头部（第一个元素） E removeFirst() 从此列表中删除并返回第一个元素。 E removeLast() 移除并返回此列表中的最后一个元素。
/
class MyQue{
Deque dq = new LinkedList();
//定义一个方法，存数据进入队列
public void adds( int val){
//若是当前滑动窗口添加的元素大于队列中右端的元素，则将当前队列入口所有小于他的元素弹出,并存入此数据
while( ! dq.isEmpty() && val > dq.getLast()){
dq.removeLast();
}
dq.add(val);
}
//定义一个方法，弹出数据
public void polls(int val){
//如果当前滑动窗口滑出的数据和队列出口数据相等，则出口数据被弹出；
if(dq.peek().equals(val)){
dq.poll();
}
}
//定义一个方法，检索最后一个数据
public int peek(){
return dq.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//定义一个对象
MyQue dq = new MyQue();
//1.先将前K个数据放进队列
for( int i = 0; i < k; i++){
dq.adds(nums[i]);
}
int[] result = new int[nums.length-k+1];//存放每次滑动窗口时的最大值
int num = 0;
result[num] = dq.peek();
num++;
//2.滑动窗口,添加数据和弹出数据
for(int i = k; i < nums.length; i++){
dq.adds(nums[i]);
dq.polls(nums[i - k]);
result[num] = dq.peek();
num++;
}
//3.返回每次滑动窗口时的最大值
return result;
}
}
2.2.3 优先队列（未完）
-
实现方式：
-
- 利用有序数组实现：删除最大项数据的时间复杂度为O(1),但是插入需要O（n)。
- 利用堆来实现：（后面会讲到）插入和删除都是O(logN)。
-
算法题：
前 K 个高频元素
2.3 用栈实现队列题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
链接：https://leetcode.cn/problems/implement-queue-using-stacks
- 思路：使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
- 在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
如果进栈和出栈都为空的话，说明模拟的队列为空了。
class MyQueue {
Stack stackOut;
Stack stackIn;
public MyQueue() {
stackIn = new Stack();//进栈
stackOut = new Stack();//出栈
}
public void push(int x) {
//进栈时直接压入输入栈
stackIn.push(x);
// stackIn.push(x);
}
public int pop() {
//出栈时，如果输出栈不为空，则直接出栈
if( !stackOut.isEmpty()){
return stackOut.pop();
}else {
//如果输出栈为空,且输入栈不为空，则将输入栈中所有元素都放进输出栈
while( !stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
return stackOut.pop();
//若输入栈也为空，则队列为空
}
}
public int peek() {
if( !stackOut.isEmpty()){
return stackOut.peek();
}else {
while( !stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
return stackOut.peek();
//若输入栈也为空，则队列为空
}
}
public boolean empty() {
return (stackOut.isEmpty() && stackIn.isEmpty());
}
}
2.4 用队列实现栈
题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
链接：https://leetcode.cn/problems/implement-stack-using-queues
- 思路1：用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
- 思路2：一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。
class MyStack {
Deque dq;
public MyStack() {
dq = new LinkedList<>();
}
public void push(int x) {
//直接入栈
dq.add(x);
}
public int pop() {
//将所有元素（除队列末尾元素）逐一弹出，并重新推进队列中
while(dq.size() != 1){
dq.add(dq.remove());
}
//弹出首段元素
return dq.poll();
}
public int top() {
return dq.peekFirst();
}
public boolean empty() {
return dq.isEmpty();
}
}
