## 栈
特点：后进先出（LIFO）
出栈入栈都是O(1)内完成
可以用一个单链表来实现
## leet-code练手
### 20. 有效的括号
~~~
package com.mango.leet.code.simple;
/**
* 20. 有效的括号
*/
import java.util.Stack;
/**
* 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
*
* 有效字符串需满足：
*
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
*
*
* 示例 1：
*
* 输入：s = "()"
* 输出：true
* 示例 2：
*
* 输入：s = "()[]{}"
* 输出：true
* 示例 3：
*
* 输入：s = "(]"
* 输出：false
* 示例 4：
*
* 输入：s = "([)]"
* 输出：false
* 示例 5：
*
* 输入：s = "{[]}"
* 输出：true
*
*
* 提示：
*
* 1 <= s.length <= 104
* s 仅由括号 '()[]{}' 组成
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/valid-parentheses
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class LC20 {
public static void main(String[] args) {
System.out.println((int)'(');
System.out.println((int)')');
System.out.println((int)'{');
System.out.println((int)'}');
System.out.println((int)'[');
System.out.println((int)']');
System.out.println(new Solution().isValid("(){}}{"));
}
static class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack();
for(int i=0;i<s.length();i++){
if(stack.isEmpty()){
stack.push(s.charAt(i));
continue;
}
char c = s.charAt(i);
Character character = stack.pop();
if(character == ']' || character == '}' || character == ')'){
return false;
}
if((character == '[' && c == ']') ||
(character == '{' && c == '}') ||
(character == '(' && c == ')')){
// 括号匹配，并且左括号在前
}else{
stack.push(character);
stack.push(c);
}
}
return stack.isEmpty();
}
public boolean isValid2(String s) {
Stack<Character> stack = new Stack();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c == '['){
stack.push(']');
}else if(c == '{'){
stack.push('}');
}else if(c == '('){
stack.push(')');
}else if(!stack.isEmpty() && c != stack.peek()){
return false;
}else {
stack.pop();
}
}
return stack.isEmpty();
}
// 自己用数组加下标模拟栈，不用api
public boolean isValid3(String s) {
int l = s.length();
char []st = new char[l];
int top = -1;
for(int i = 0;i < l;i++){
char s_in = s.charAt(i);
if(s_in == '(' || s_in == '[' || s_in == '{'){
top++;
st[top] = s_in;
}
else{
if(top < 0){
return false;
}
if(s_in == ')' && st[top] != '('){
return false;
}
if(s_in == ']' && st[top] != '['){
return false;
}
if(s_in == '}' && st[top] != '{'){
return false;
}
top--;
}
}
if(top > -1){
return false;
}
return true;
}
}
}
/**
* 2022-03-02
* 思路：
* 利用栈先入后出的特点，如果括号匹配就出站，不匹配且做括号在前的就先入栈
*/
~~~
#### 739每日温度
~~~
package com.mango.leet.code.middle;
/**
* 739. 每日温度
*/
import java.util.Arrays;
import java.util.Stack;
/**
* 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
*
*
*
* 示例 1:
*
* 输入: temperatures = [73,74,75,71,69,72,76,73]
* 输出: [1,1,4,2,1,1,0,0]
* 示例 2:
*
* 输入: temperatures = [30,40,50,60]
* 输出: [1,1,1,0]
* 示例 3:
*
* 输入: temperatures = [30,60,90]
* 输出: [1,1,0]
*
*
* 提示：
*
* 1 <= temperatures.length <= 105
* 30 <= temperatures[i] <= 100
*
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/daily-temperatures
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class LC739 {
public static void main(String[] args) {
int[] arr = new int[]{89,62,70,58,47,47,46,76,100,70};
System.out.println(Arrays.toString(new Solution().dailyTemperatures(arr)));
}
static class Solution {
// [73,74,75,71,69,72,76,73]
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
Stack<Integer> stack = new Stack<Integer>();
for(int i=0;i<temperatures.length;i++){
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
return result;
}
}
}
/**
* 2022-03-03
* 思路：
* 1. 将下标压入栈里
* 2. 遍历比较当前下标数据A和栈内下标数据B，如果A>B,则出栈并记录站内下标的变暖天数，并将A下标压入站内
* 3. 遍历站内数据和当前下标数据做对比，重复步骤2
* 4. 如果栈空或者当前值小于站内下标对应值，则入栈
*/
~~~
- Redis来回摩擦
- redis的数据结构SDS和DICT
- redis的持久化和事件模型
- Java
- 从何而来之Java IO
- 发布Jar包到公共Maven仓库
- Java本地方法调用
- 面试突击
- Linux
- Nginx
- SpringBoot
- Springboot集成Actuator和SpringbootAdminServer监控
- SpringCloud
- Spring Cloud初识
- Spring Cloud的5大核心组件
- Spring Cloud的注册中心
- Spring Cloud注册中心之Eureka
- Spring Cloud注册中心之Consul
- Spring Cloud注册中心之Nacos
- Spring Cloud的负载均衡之Ribbon
- Spring Cloud的服务调用之Feign
- Spring Cloud的熔断器
- Spring Cloud熔断器之Hystrix
- Spring Cloud的熔断器监控
- Spring Cloud的网关
- Spring Cloud的网关之Zuul
- Spring Cloud的配置中心
- Spring Cloud配置中心之Config Server
- Spring Cloud Config配置刷新
- Spring Cloud的链路跟踪
- Spring Cloud的链路监控之Sleuth
- Spring Cloud的链路监控之Zipkin
- Spring Cloud集成Admin Server
- Docker
- docker日常基本使用
- docker-machine的基本使用
- Kubernetes
- kubernetes初识
- kubeadm安装k8s集群
- minikube安装k8s集群
- k8s的命令行管理工具
- k8s的web管理工具
- k8s的相关发行版
- k3s初识及安装
- rancher的安装及使用
- RaspberryPi
- 运维
- 域名证书更新
- 腾讯云主机组建内网
- IDEA插件开发
- 第一个IDEA插件hello ide开发
- 千呼万唤始出来的IDEA笔记插件mdNote
- 大刚学算法
- 待整理
- 一些概念和知识点
- 位运算
- 数据结构
- 字符串和数组
- LC242-有效的字母异位词
- 链表
- LC25-K个一组翻转链表
- LC83-删除有序单链表重复的元素
- 栈
- LC20-有效的括号
- 队列
- 双端队列
- 优先队列
- 树
- 二叉树
- 二叉树的遍历
- 二叉树的递归序
- 二叉树的前序遍历（递归）
- 二叉树的前序遍历（非递归）
- 二叉树的中序遍历（递归）
- 二叉树的中序遍历（非递归）
- 二叉树的后序遍历（递归）
- 二叉树的后序遍历（非递归）
- 二叉树的广度优先遍历（BFS）
- 平衡二叉树
- 二叉搜索树
- 满二叉树
- 完全二叉树
- 二叉树的打印（二维数组）
- 树的序列化和反序列化
- 前缀树
- 堆
- Java系统堆优先队列
- 集合数组实现堆
- 图
- 图的定义
- 图的存储方式
- 图的Java数据结构（邻接表）
- 图的表达方式及对应场景创建
- 图的遍历
- 图的拓扑排序
- 图的最小生成树之Prim算法
- 图的最小生成树之Kruskal算法
- 图的最小单元路径之Dijkstra算法
- 位图
- Java实现位图
- 并查集
- Java实现并查集
- 滑动窗口
- 单调栈
- 排序
- 冒泡排序BubbleSort
- 选择排序SelectSort
- 插入排序InsertSort
- 插入排序InsertXSort
- 归并排序MergeSort
- 快速排序QuickSort
- 快速排序优化版QuickFastSort
- 堆排序HeapSort
- 哈希Hash
- 哈希函数
- guava中的hash函数
- hutool中的hash函数
- 哈希表实现
- Java之HashMap的实现
- Java之HashSet的实现
- 一致性哈希算法
- 经典问题
- 荷兰国旗问题
- KMP算法
- Manacher算法
- Go