目录
单调队列单调栈
队列和双端队列基础
剑指offer59②队列的最大值
剑指 Offer 59 - I. 滑动窗口的最大值
栈 基础
最小栈
42.接雨水 难度 困难
739.每日温度 难度 中等
队列和栈
剑指Offer09用两个栈实现队列
单调队列单调栈
队列和双端队列基础
Queue中offer()入队，poll()出队，peek()查询头部元素。offer，add区别，poll，remove区别，peek，element区别,前面对空操作不会抛出异常。
deque是双端队列。
Deque<Integer> deque = new LinkedList<>();
deq.peekLast()返回此双端队列表示的最后一个元素，否则当此双端队列为“空白”时返回null。deq.peekfirst()检索链表的第一个元素，初始元素或开始元素，但不会从列表中删除第一个元素。
deq.offerLast(value)指定元素添加在列表的末尾，pollLast()返回列表的最后一个元素并从列表中移除。
pollFirst()检索并移除此列表的第一个元素，或者如果此列表为空，则返回null。
单调栈含义就是栈内的元素是单调的，我们这两个题目用到的都是递减栈（相同也可以），我们依次将元素压入栈，如果当前元素小于等于栈顶元素则入栈，如果大于栈顶元素则先将栈顶不断出栈，直到当前元素小于或等于栈顶元素为止，然后再将当前元素入栈。
剑指offer59②队列的最大值
使用辅助双端队列deq
入队操作解释：入队queue直接入队，dequeue先比较最后一个元素，比要入队元素小的先出队（从后面），然后再入队deq.offerLast(value);
返回队头元素解释：如果que为空返回-1，不为空 如果que和deq的第一个元素相等（取第一个元素写法不同，比较用equal que.peek().equals(deq.peekFirst()) ）
我们之前说过的队列，遵守先进先出的规则，双端队列则可以从队头出队，也可以从队尾出队。队尾入队。
我们可以用双端队列做辅助队列，用辅助队列来保存当前队列的最大值。我们同时定义一个普通队列和一个双端单调队列。普通队列就正常执行入队，出队操作。max_value 操作则返回咱们的双端队列的队头即可。
class MaxQueue {
//普通队列
Queue<Integer> que;
//双端队列
Deque<Integer> deq;
public MaxQueue() {
que = new LinkedList<>();
deq = new LinkedList<>();
}
//获取最大值值，返回我们双端队列的对头即可，因为我们双端队列是单调递减的嘛
public int max_value() {
return deq.isEmpty() ? -1 : deq.peekFirst();
}
//入队操作
public void push_back(int value) {
que.offer(value);
//维护单调递减
while (!deq.isEmpty() && value > deq.peekLast()){
deq. pollLast();
}
deq.offerLast(value);
}
//返回队头元素，此时有个细节，我们需要用equals
//这里需要使用 equals() 代替 == 因为队列中存储的是 int 的包装类 Integer
public int pop_front() {
if(que.isEmpty()) return -1;
if (que.peek().equals(deq.peekFirst())) {
deq.pollFirst();
}
return que.poll();
}
}
public int pop_front() {
if(que.isEmpty()) return -1; //que为空
if (que.peek().equals(deq.peekFirst())) { //比较如果第一个元素相同
deq.pollFirst(); //deq第一个元素出队
}
return que.poll(); //que第一个元素出队
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组
nums
和滑动窗口的大小
k
，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
来源：力扣（LeetCode）
和上一题类似
1.想将我们第一个窗口的所有值存入单调双端队列中，单调队列里面的值为单调递减的。如果发现队尾元素小于要加入的元素，则将队尾元素出队，直到队尾元素大于新元素时，再让新元素入队，目的就是维护一个单调递减的队列。
2.我们将第一个窗口的所有值，按照单调队列的规则入队之后，因为队列为单调递减，所以队头元素必为当前窗口的最大值，则将队头元素添加到数组中。
3.移动窗口，判断当前窗口前的元素是否和队头元素相等，如果相等则出队。
4.继续然后按照规则进行入队，维护单调递减队列。
5.每次将队头元素存到返回数组里。
5.返回数组
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (len == 0) {
return nums;
}
int[] arr = new int[len - k + 1];
int arr_index = 0;
//我们需要维护一个单调递增的双向队列
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
deque.removeLast(); //队头保留最大的 为什么用remove不用poll？
}
deque.offerLast(nums[i]); //值小的出队完，入队
}
arr[arr_index++] = deque.peekFirst(); //数组赋第一个值
for (int j = k; j < len; j++) { //j指针从k位置开始遍历到最后 滑动窗口
if (nums[j - k] == deque.peekFirst()) { //j-k是当前窗口的第一个的前一个
deque.removeFirst(); //最大值是前一个窗口的，删除
}
while (!deque.isEmpty() && deque.peekLast() < nums[j]) { //nums[j]要进，队现有的后面的比它小的都出队 （固定写法）
deque.removeLast();
}
deque.offerLast(nums[j]); //进队
arr[arr_index++] = deque.peekFirst(); //数组赋剩余的值，
}
return arr;
}
}
为什么要比较相同？后来补充：因为不能把即将遍历的窗口中的最大值删掉，只有最大值是前一个窗口的才删
if (nums[j - k] == deque.peekFirst()) {
deque.removeFirst();
}
栈 基础
Stack<Integer> A,B; 定义栈
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
B.isEmpty()//判断空 B.peek()//栈顶值 不删除
B.push(x)//入栈 A.peek()//出线
最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"] > [[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
和队列的最大值类似，使用辅助栈
1.我们执行入栈操作时，先观察需要入栈的元素是否小于栈 B 的栈顶元素，如果小于则两个栈都执行入栈操作。
2.栈 B 的栈顶元素则是栈 A 此时的最小值。则 getMin() 只需返回栈 B 的栈顶元素即可。
3.出栈时，需要进行对比，若栈 A 和栈 B 栈顶元素相同，则同时出栈，出栈好 B 的栈顶保存的仍为此时栈 A 的最小元素
class MinStack {
//初始化
Stack<Integer> A,B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
//入栈，如果插入值，当前插入值小于栈顶元素，则入栈，栈顶元素保存的则为当前栈的最小元素
public void push(int x) {
A.push(x);
if (B.isEmpty() || B.peek() >= x) { //B空也push
B.push(x); //要存最小，所以＞＝
}
}
//出栈，如果A出栈等于B栈顶元素，则说明此时栈内的最小元素改变了。
//这里需要使用 equals() 代替 == 因为 Stack 中存储的是 int 的包装类 Integer
public void pop() {
if (A.pop().equals(B.peek()) ) { //pop删除（和remove对应） peek返回元素（和element对应）
B.pop();
}
}
//A栈的栈顶元素
public int top() {
return A.peek();
}
//B栈的栈顶元素
public int getMin() {
return B.peek();
}
}
//入栈，如果插入值，当前插入值小于栈顶元素，则入栈，栈顶元素保存的则为当前栈的最小元素
public void push(int x) {
A.push(x);
if (B.isEmpty() || B.peek() >= x) {
B.push(x);
}
}
//出栈，如果A出栈等于B栈顶元素，则说明此时栈内的最小元素改变了。
//这里需要使用 equals() 代替 == 因为 Stack 中存储的是 int 的包装类 Integer
public void pop() {
if (A.pop().equals(B.peek()) ) {
B.pop();
}
}
但是没有比较之后栈顶元素出栈的操作，为什么队列有？后来补充：没想通
42.接雨水 难度 困难
单调 递减栈，从最低到最高，按层算
只懂思路
739.每日温度 难度 中等
上题的简化版。T是给定的温度数组，自己定义stack通过下标的运算计算出天数，T和stack通过下标联系起来。
初始i=0，不会运行while，直接push（i） 学习这个写法
for (int i = 0; i < len; i++) {
//单调栈
while (!stack.isEmpty() && T[i] > T[stack.peek()]){
arr[stack.peek()] = i - stack.pop();
}
stack.push(i);
}
队列和栈
剑指Offer09用两个栈实现队列
class CQueue {
//初始化两个栈
Stack<Integer> stack1,stack2;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
//入队，我们往第一个栈压入值
public void appendTail (int value) {
stack1.push(value);
}
//出队
public int deleteHead() {
//大家可以自己思考一下为什么if条件为stack2.isEmpty(),细节所在
if (stack2.isEmpty()) {
//如果此时A栈没有值，则直接-1，我们可以看示例
if (stack1.isEmpty()) {
return -1;
}
//将A栈的值，压入B栈中
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
核心的出队代码
//出队
public int deleteHead() {
//大家可以自己思考一下为什么if条件为stack2.isEmpty(),细节所在
//思考这不很简单吗
if (stack2.isEmpty()) {
//如果此时A栈没有值，则直接-1，我们可以看示例
if (stack1.isEmpty()) {
return -1;
}
//将A栈的值，压入B栈中
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
鼓感觉还行 18:02