栈和队列
- stack
- queue
- deque
deque
- priorityQueue
插入：O（1）
查找：O（logN）
解题技巧总结
- 使用栈解决最具相关性/最近相关性(重复性)问题
- 使用queue解决先来后到问题
- 用栈实现队列：用两个栈解决
- 用队列实现栈：用两个队列解决
有效的括号
题号20
使用栈
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
return stack.isEmpty();
}
}
最小栈
题号155
使用辅助栈
解题思路
借用一个辅助栈min_stack，用于存获取stack中最小值。
算法流程
- push()方法： 每当push()新值进来时，如果 小于等于 min_stack栈顶值，则一起push()到min_stack，即更新了栈顶最小值；
- pop()方法： 判断将pop()出去的元素值是否是min_stack栈顶元素值（即最小值），如果是则将min_stack栈顶元素一起pop()，这样可以保证min_stack栈顶元素始终是stack中的最小值。
- getMin()方法： 返回min_stack栈顶即可。
min_stack作用分析：
- min_stack等价于遍历stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。
- 相当于给stack中的降序元素做了标记，每当pop()这些降序元素，min_stack会将相应的栈顶元素pop()出去，保证其栈顶元素始终是stack中的最小元素。
复杂度分析
- 时间复杂度 O(1)O(1) ：压栈，出栈，获取最小值的时间复杂度都为 O(1)O(1) 。
- 空间复杂度 O(N)O(N) ：包含 NN 个元素辅助栈占用线性大小的额外空间。
class MinStack {
private Stack<Integer> data;
private Stack<Integer> helper;
/** initialize your data structure here. */
public MinStack() {
data=new Stack<>();
helper=new Stack<>();
}
public void push(int val) {
data.add(val);
if(helper.isEmpty()||helper.peek()>=val){
helper.add(val);
}
}
public void pop() {
if(!data.isEmpty()){
int top=data.pop();
if(top==helper.peek()){
helper.pop();
}
}
}
public int top() {
return data.peek();
}
public int getMin() {
return helper.peek();
}
}
84 柱状图的最大面积
- 利用栈存放尚未找到右边界的下标，当找到高度比自身小的柱形，则出栈并记录自身宽度，栈中始终保存当前尚未找到右边界，也就是最小高度的柱形下标。
- 利用两个数组记录当前下标对应的柱状所能组成最大面积的宽度的左右下标，用于计算面积。
class Solution {
public int largestRectangleArea(int[] heights) {
int n=heights.length;
int[] left=new int[n];
int[] right=new int[n];
Arrays.fill(right,n);
Stack<Integer> stack=new Stack<>();
for(int i=0;i<n;i++){
while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
right[stack.peek()]=i;
stack.pop();
}
left[i]=stack.isEmpty()?-1:stack.peek();
stack.push(i);
}
int area=0;
for(int i=0;i<n;i++){
area=Math.max(area,((right[i]-left[i]-1)*heights[i]));
}
return area;
}
}
239 滑动窗口最大值
思路：
遍历数组，将 数 存放在双向队列中，并用 L,R 来标记窗口的左边界和右边界。队列中保存的并不是真的 数，而是该数值对应的数组下标位置，并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。刚开始遍历时，L 和 R 都为 0，有一个形成窗口的过程，此过程没有最大值，L 不动，R 向右移。当窗口大小形成时，L 和 R 一起向右移，每次移动时，判断队首的值的数组下标是否在 [L,R] 中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。
示例：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
初始状态：L=R=0,队列:{}
i=0,nums[0]=1。队列为空,直接加入。队列：{1}
i=1,nums[1]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：{3}
i=2,nums[2]=-1。队尾值为3，-1<3，直接加入。队列：{3,-1}。此时窗口已经形成，L=0,R=2，result=[3]
i=3,nums[3]=-3。队尾值为-1，-3<-1，直接加入。队列：{3,-1,-3}。队首3对应的下标为1，L=1,R=3，有效。result=[3,3]
i=4,nums[4]=5。队尾值为-3，5>-3，依次弹出后加入。队列：{5}。此时L=2,R=4，有效。result=[3,3,5]
i=5,nums[5]=3。队尾值为5，3<5，直接加入。队列：{5,3}。此时L=3,R=5，有效。result=[3,3,5,5]
i=6,nums[6]=6。队尾值为3，6>3，依次弹出后加入。队列：{6}。此时L=4,R=6，有效。result=[3,3,5,5,6]
i=7,nums[7]=7。队尾值为6，7>6，弹出队尾值后加入。队列：{7}。此时L=5,R=7，有效。result=[3,3,5,5,6,7]
- 单调队列也可以存值，题解中存的是下标。
- 如果存值的话，每次只有新元素 大于 队列尾部的元素时，才去移除队列尾部的元素
- 窗口左侧移出去的元素如果等于队列头部的元素，则removeFirst。
举个例子： "543321" ，k=3 - 队列存值的情况下，如果不将两个3都加入，当第一个3被移出时，会导致321的最大值变为2，因为3已经被移出了，因此存值的话，需要新的元素大于队列尾部元素再去移除队列尾部的元素。
- 队列存下标的情况下，就可以只存一个3（存第二个），因为通过下标就能判断出移出的是第一个3还是第二个3。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res=new int[nums.length-k+1];
Deque<Integer> deque=new LinkedList<>();
for(int i=0;i<nums.length;i++){
while(!deque.isEmpty()&&deque.peekLast()<nums[i]){
deque.removeLast();
}
deque.addLast(nums[i]);
if(i>=k&&nums[i-k]==deque.peekFirst()){
deque.removeFirst();
}
if(i>=k-1){
res[i-k+1]=deque.peekFirst();
}
}
return res;
}
}
网友评论