1. 用队列实现栈或双栈实现队列相关
- 一个队列实现栈：要弹出，队尾先存入队首
class MyStack {
/*
一个队列实现栈功能
8.23
*/
LinkedList<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
//入队尾
queue.addLast(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
//要弹出栈顶，队尾先存入队首
for(int i=0;i<queue.size()-1;i++){
queue.addLast(queue.pollFirst());
}
return queue.pollFirst();
}
/** Get the top element. */
public int top() {
//要返回栈顶，队尾先存入队首
for(int i=0;i<queue.size()-1;i++){
queue.addLast(queue.pollFirst());
}
//先接收队首
int pre = queue.pollFirst();
//重新入队尾
queue.addLast(pre);
return pre;
}
/** Returns whether the stack is empty. */
public boolean empty() {
if(queue.size() == 0){
return true;
}else{
return false;
}
}
}
- 双栈实现队列
class MyQueue {
/*
双栈实现队列，栈先进后出，队列先进先出
8.23
*/
Stack<Integer> stack1;
Stack<Integer> stack2;
/** Initialize your data structure here. */
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
//stack1直接入栈
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
//当stack2为空stack1不为空时，stack2存入stack1的弹出，实现先进先出
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
if(stack2.isEmpty()){
return -1;
}else{
return stack2.pop();
}
}
/** Get the front element. */
public int peek() {
//同pop
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
if(stack2.isEmpty()){
return -1;
}else{
return stack2.peek();
}
}
/** Returns whether the queue is empty. */
public boolean empty() {
//判断stack1和stack2都为空
return stack1.isEmpty() && stack2.isEmpty();
}
}
- 最小栈：包含min的栈
class MinStack {
/*
最小栈：双栈维护min
8.24
*/
Stack<Integer> stack;
Stack<Integer> min;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
min = new Stack<>();
}
public void push(int x) {
//stack直接存
stack.push(x);
//min的栈顶维护min
if(min.isEmpty() || min.peek() >= x){
min.push(x);
}
}
public void pop() {
//如果stack.pop等于min.peek。min弹出栈顶
if(stack.pop().equals(min.peek())){
min.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
- 最大队列：
class MaxQueue {
/*
队列的最大值
7.27
*/
LinkedList<Integer> queue;
//max队首维护最大值
LinkedList<Integer> max;
public MaxQueue() {
queue = new LinkedList<>();
max = new LinkedList<>();
}
public int max_value() {
//如果queue为空，返回-1，否则返回max队首
if(queue.isEmpty()){
return -1;
}else{
return max.peekFirst();
}
}
public void push_back(int value) {
queue.addLast(value);
//因为max队列的队首维护最大值，如果当前元素比队尾大，弹出队尾，将当前元素入队尾，形成从大到小排序的队列
while(!max.isEmpty() && max.peekLast() <= value){
max.removeLast();
}
max.addLast(value);
}
public int pop_front() {
if(queue.isEmpty()){
return -1;
}
//先接收队列弹出的队首
int result = queue.removeFirst();
//判断弹出的元素与max队列维护的最大值是否相等，如果相等，max队列也要弹出队首
if(result == max.peekFirst()){
max.removeFirst();
}
//返回队列的弹出
return result;
}
}
2. 括号匹配类型
- 有效括号(老经典了，好几次笔试都碰到了)
class Solution {
public boolean isValid(String s) {
/*
有效括号
8.24
*/
//单调栈，当遇到左半括号时，存入右半括号，如果栈为空，说明没有存入，如果栈弹出的不等于下一个字符(右半括号)
Stack<Character> stack = new Stack<>();
char[] str = s.toCharArray();
for(int i=0;i<str.length;i++){
if(str[i] == '('){
stack.push(')');
}else if(str[i] == '['){
stack.push(']');
}else if(str[i] == '{'){
stack.push('}');
}else if(stack.isEmpty() || stack.pop() != str[i]){
//如果栈为空，说明无法存入右半。如果栈顶不等于下一次(右半括号)，说明无法闭合
return false;
}
}
return stack.isEmpty();
}
}
- 最长有效括号：
class Solution {
public int longestValidParentheses(String s) {
/*
最长有效括号
8.23
*/
//先预存-1，用于判断字符串是否是"))"类型
//当遇到"("时，先将其索引入栈
//当遇到")"时，弹出栈顶元素，表示已经使用右括号匹配左括号，形成一个闭合括号
//如果弹出之后栈为空，说明字符串可能是:"))"这种形式，表明当前右括号无法闭合，将其索引重新入栈
//如果弹出之后栈不为空，当前索引 - 栈顶。如"(()"，当遇到)时，弹出栈顶元素1，当前索引2 - 0 = 2，就是最长有效括号
Stack<Integer> stack = new Stack<>();
stack.push(-1);
char[] str = s.toCharArray();
int result = 0;
for(int i=0;i<str.length;i++){
if(str[i] == '('){
stack.push(i);
}else{
//一定要先弹出
stack.pop();
if(stack.isEmpty()){
stack.push(i);
}else{
result = Math.max(result,i - stack.peek());
}
}
}
return result;
}
}
3. 单调栈
- 验证栈弹出和栈存入
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
/*
验证栈序列
单调栈
8.24
*/
Stack<Integer> stack = new Stack<>();
int index = 0;
//遍历入栈序列
for(int i : pushed){
//先入栈
stack.push(i);
//while循环判断，如果相等，弹出栈顶
while(!stack.isEmpty() && stack.peek() == popped[index]){
index++;
stack.pop();
}
}
return stack.isEmpty();
}
}
- 每日温度
class Solution {
public int[] dailyTemperatures(int[] T) {
/*
每日温度
7.26
*/
//单调栈，栈存索引，当栈顶比当前小时，计算差值
Stack<Integer> stack = new Stack<>();
int[] result = new int[T.length];
for(int i=0;i<T.length;i++){
//栈比数组慢，当栈顶小于当前数组元素时，说明升温，弹出栈顶，计算其索引差值，存入到result数组对应的索引位置(不是顺序存储啊)
while(!stack.isEmpty() && T[i] > T[stack.peek()]){
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
return result;
}
}
- 柱状图的最大矩形
class Solution {
public int largestRectangleArea(int[] heights) {
/*
柱状图中最大的矩形
7.24
*/
//单调栈，先复制数组，在头尾添加一个高度为1的柱体
//判断空
if(heights.length == 0){
return 0;
}
//复制数组，在头尾插入一个高度为0的主题
int[] temp = new int[heights.length+2];
//从1到temp.length
System.arraycopy(heights,0,temp,1,heights.length);
Stack<Integer> stack = new Stack<>();
int result = 0;
for(int i=0;i<temp.length;i++){
//while栈顶比当前大，找到第一个比当前小的柱体，计算其体积
while(!stack.isEmpty() && temp[i] < temp[stack.peek()]){
int high = temp[stack.pop()];
int widht = i - stack.peek() - 1;
result = Math.max(high*widht,result);
}
stack.push(i);
}
return result;
}
}
- 接雨水(解法不属于单调栈，但还是一类型的经典题目，所以放在一起总结)
class Solution {
public int trap(int[] height) {
/*
接雨水
7.24
*/
//左右数组存最大值，提取左右数组的最小值，如果最小值比当前高度高，叠加雨水量
//判断空
if(height.length == 0){
return 0;
}
int[] left_max = new int[height.length];
int[] right_max = new int[height.length];
//从左往右搜，提取最大值，从1开始(0不能存水)
for(int i=1;i<height.length;i++){
left_max[i] = Math.max(height[i-1],left_max[i-1]);
}
//从右往左搜，提取最大值，从len-2开始(len-1不能存水)
for(int i=height.length-2;i>=0;i--){
right_max[i] = Math.max(height[i+1],right_max[i+1]);
}
int result = 0;
//从1到len-2
for(int i=1;i<height.length-1;i++){
int low = Math.min(left_max[i],right_max[i]);
//如果low比当前高度高，说明可以存水，叠加高度差
if(low > height[i]){
result += low-height[i];
}
}
return result;
}
}
- 滑动窗口的最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
/*
滑动窗口的最大值
8.24
*/
//创建窗口数组
int len = nums.length;
int[] result = new int[len-k+1];
//创建队列
LinkedList<Integer> queue = new LinkedList<>();
int index = 0;
for(int i=0;i<nums.length;i++){
//队尾维护最大值
while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){
queue.removeLast();
}
queue.addLast(i);
//当滑动窗口左边界等于队首时，说明要右移，队列弹出队首
if(i-k == queue.peekFirst()){
queue.removeFirst();
}
//存入：当形成滑动窗口之后，添加队首对应的元素
if(i >= k-1){
result[index++] = nums[queue.peekFirst()];
}
}
return result;
}
}
