文章目录
- 栈和队列
- stack Class
- queue Interface
- Deque Interface
- add 和 push
- Priority Queue -- Class
- 题目
- codestyle
- IDEA 操作
- 快捷键
- 选择
- 代码生成类
栈和队列
stack Class
google stack java 8/12
empty()
peek()
pop()
push(E item)
search(Object o)
最近相关性会用到栈
queue Interface
- Throws exception:
add(e)
remove()
element() - Returns special value:
offer()
peek()
poll()
大多滑动窗口的题目，用队列解决即可。
Deque Interface
ArrayDeque,LinkedList…
API与queue类似，乘二。
分为First和Last。
add 和 push
当我们使用Deque实现栈的功能时，注意要用push（==addFirst）。不要写成add（==addLast）
LinkedList实现的Deque，peek，pop，push都是在列表头进行操作。
Priority Queue – Class
- 插入O(1)
- 取出O(lonN)- 按照元素的优先性
- 底层具体实现多样，可以用heap堆、bst、treap
题目
- 有效的括号
class Solution {
public boolean isValid(String s) {
Deque < Character > deque = new LinkedList<>();//注意实例化的写法
//用了char，后续都要用单引号，不能用双引号String
char ch ;
for ( int i = 0 ; i < s.length() ; i++ ){
ch = s.charAt(i);//charAt的写法
if( ch == '('){
deque.push(')');//这里deque是push，不是append。更不是add。
}else if(ch == '['){
deque.push(']');
}else if(ch =='{' ){
deque.push('}');
}//下面一行搞错了，如果过程中deque就空了，也要返回false。所以不能是且，是或
//else if(deque.isEmpty()!=false && ch != deque.peek()){
else if(deque.isEmpty() || ch != deque.peek()){
return false;
}else{
deque.pop();
}
}
return deque.isEmpty();
}
}
- 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
class MinStack {
// 两个栈即可实现
private Stack<Integer> stack;
private Stack<Integer> min_stack;
public MinStack() {
stack = new Stack<>();
min_stack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(min_stack.isEmpty() || val<=min_stack.peek() )
min_stack.push(val);
}
public void pop() {
if(stack.pop().equals(min_stack.peek()))
min_stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_stack.peek();
}
}
- 柱状图中的最大矩形面积
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
class Solution {
public int largestRectangleArea(int[] heights) {
//暴力：遍历每一个，左右到比他更小就停，总结矩形面积。On方
//单调栈
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int maxArea = 0;
for(int i = 0 ; i <heights.length ; i ++){
//每次有新元素就和栈顶比较大小，直到入栈。
//栈顶大则pop，且计算pop的index对应的area
//栈顶小则入栈，不用计算area
while(stack.peek() != -1 && heights[stack.peek()] > heights[i]){
int index = stack.pop() ;
maxArea = Math.max( maxArea , heights[index] * (i-stack.peek()-1));
}
//千万别忘了入栈
stack.push(i);
}
while(stack.peek() != -1){
int index = stack.pop() ;
//错误写法，计算错误
//maxArea = Math.max( maxArea , heights[index] * (index-stack.peek()-1));
maxArea = Math.max( maxArea , heights[index] * (heights.length-stack.peek()-1));
}
return maxArea;
}
}
优化方法： 单调栈
每一个点要有左右边界。
为了找边界，可以用栈。
维护一个栈，栈里元素从小到大排列。
（实际上可以是栈里放index，随时可以查到对应的height，height才是从小到大排列）
向右走一位，进行至少一次判断。
发现新高度小于栈顶，则说明有一个右边界可以确定。
而左边界一直是栈里该元素的下面一位（下一位是他左边刚好比他小的那一个）的下标。
Area=(right- left -1)*index;
pop之后继续判断，若新高度小于栈顶，重复上述过程。直到新高度大于栈顶高度，新高度入栈。
栈底用 -1
则left = （-1）时公式不变，边界处理一致。
class Solution {
public int largestRectangleArea(int[] heights) {
//暴力：遍历每一个，左右到比他更小就停，总结矩形面积。On方
//单调栈
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int maxArea = 0;
for(int i = 0 ; i <heights.length ; i ++){
//每次有新元素就和栈顶比较大小，直到入栈。
//栈顶大则pop，且计算pop的index对应的area
//栈顶小则入栈，不用计算area
while(stack.peek() != -1 && heights[stack.peek()] > heights[i]){
maxArea = Math.max( maxArea , heights[stack.pop()] * (i-stack.peek()-1));
}
//千万别忘了入栈
stack.push(i);
}
while(stack.peek() != -1){
//错误写法，计算错误
//maxArea = Math.max( maxArea , heights[index] * (index-stack.peek()-1));
maxArea = Math.max( maxArea , heights[stack.pop()] * (heights.length-stack.peek()-1));
}
return maxArea;
}
}
codestyle
每一个括号和运算符前后都应该加空格。
IDEA 操作
快捷键
Home End键——行头行尾
删除行 ctrl + Y
选择
扩选 ctrl + W
缩选 ctrl + Shift + W
代码生成类
Alt+Insert：在目录中使用该快捷键可以新建包，文件，类。在 java 文件中可以进行 setter，getter，构造方法，toString等方法生成，生成方法覆盖（重写）。
Ctrl+Shift+空格：智能代码提示，代码自动补全。可用于强制类型转换补全，new 对象补全，return 补全等。
Ctrl+Shift+Enter：自动补全代码结构。自动生成 if, do-while, try-catch, return（或方法调用） 语法正确的代码结构，比如添加括号和大括号。
