转码野生老农刷题打卡

2022-10-13打卡

20        有效的括号
Link：https://leetcode.cn/problems/valid-parentheses/
题解：https://gitee.com/vincentmliu/Al ... lidParentheses.java
耗时： 5min



笔记：
1. 循环遍历s，左括号入栈，右括号对比出栈。对不上就返回false
2. 循环结束如果栈不空（左括号多了），就返回false

时间复杂度 O(n) 扫描一次
空间复杂度 O(n) 一个stack存储sChar

2022-10-14打卡

Interview 16.26        计算器
Link：https://leetcode.cn/problems/calculator-lcci/
题解：https://gitee.com/vincentmliu/Al ... CalculatorLcci.java
耗时： 20min



笔记：
边界条件太多，要注意
1. 总体思想：两个栈，一个存数字，一个存符号。遇到数字就入栈，遇到+和-先入栈。遇到*和/，numsStack top出栈，并且和下一个数字计算结果，然后放到numStack
2. 最后扫描一次operStack, 每次pop一个oper和两个num，再peek beforeOper，如果beforOper是负数，那oper要交换符号

时间复杂度 O(n) 扫描一次，弹出一次
空间复杂度 O(n) 两个stack存储sChar

2022-10-15打卡

1047        删除字符串中的所有相邻重复项
Link：https://leetcode.cn/problems/rem ... plicates-in-string/
题解：https://gitee.com/vincentmliu/Al ... icatesInString.java
耗时： 5min


笔记：
1. 就是栈，peek顶上的元素，下一次碰到了就pop。如果下一个！= peek，那就push进去。
2. 注意细节，最后stack遍历pop出来的序列要reverse。空栈的情况下不要peek，直接push，避免抛错。


时间复杂度 O(n) 扫描一遍
空间复杂度 O(n) 需要一个栈来保存

2022-10-17打卡

Offer31        栈的压入、弹出序列
Link：https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
题解：https://gitee.com/vincentmliu/Al ... anChuXuLieLcof.java
耗时： 20min



笔记：
思路很简单，细节是魔鬼
1. 空栈必push，所以pushed index ++;
2. 如果stack top ！= popped[po]， 一直push到stack top== popped[po]; push必先执行完
3. push执行结束之后，popped不断弹出，如果stack top ！= popped[po] 返回false；
4. 注意！！！空数组直接返回true；

时间复杂度 O(n) 扫描一次，弹出一次
空间复杂度 O(n) 一个stack存储；

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

2022-10-18打卡

739        每日温度
Link：https://leetcode.cn/problems/daily-temperatures/
题解：https://gitee.com/vincentmliu/Al ... lyTemperatures.java
耗时： 1h



笔记：
面试可没有tag提示是单调栈
1. 暴力循环会超时，时间复杂度O(n²),思路就是找每个temperature后面第一个大于该temperature的
2. 单调栈，保存比当前i小的下标。遇到大于top值得temperature[i] > temperatures[top], answer[top] = i-top; 弹出top。一直到temperature[i] <= temperatures[top]或者stack为空。

时间复杂度 O(n) 入一次，弹出一次
空间复杂度 O(n) 一个stack存储；

2022-10-18打卡

42        接雨水
Link：https://leetcode.cn/problems/trapping-rain-water/
题解：https://gitee.com/vincentmliu/Al ... ppingRainWater.java
耗时： 1h



笔记：
单调栈做法
1. 从最左侧开始入栈，碰到比stack.peek小的就入栈。
2. 碰到比stack.peek大的，依次计算peek高度的水量。（current - peek - 1）* distance
3. current到移动到最后，计算完毕

时间复杂度 O(n) 入一次，弹出一次
空间复杂度 O(n) 一个stack存储；

2022-10-18打卡

84        柱状图中最大的矩形
Link：https://leetcode.cn/problems/largest-rectangle-in-histogram/
题解：https://gitee.com/vincentmliu/Al ... gleInHistogram.java
耗时： 1h



笔记：
暴力法：
1. 每个柱子遍历左右，找到height[left -1] < height[i]; height[right + 1] < height[i]。
2. 长方形的宽度就是right - left + 1；
这样的时间复杂度是O(n^2);
单调栈：
1. 用单调递增栈去找到右边第一个小于stack.peek的柱子，从左到右遍历。
2. 找到小于stack.peek的柱子后，依次从右往左计算每个stack.peek的高度。连续相同高度的直接pop，计算前面的柱子。
3. 边界条件注意，栈底的柱子肯定能延续到最左侧。

时间复杂度 O(n) 入一次，弹出一次
空间复杂度 O(n) 一个stack存储

2022-10-20打卡

Interview 03.06        动物收容所
Link：https://leetcode.cn/problems/animal-shelter-lcci/
题解：https://gitee.com/vincentmliu/Al ... malShelterLcci.java
耗时： 30min



笔记：
非要用stack实现的话，就得倒来倒去
1. 分别四个stack: catIn, catOut, dogIn, dogOut；
2. enqueue的时候检查out是否为空，不空就全都push到in中
3. 同理，dequeue的时候检查in是否为空，不空就全部push到out中
4. 注意边界条件

2022-10-21打卡

Offer 59 II        队列的最大值
Link：https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/
题解：https://gitee.com/vincentmliu/Al ... DeZuiDaZhiLcof.java
耗时： 30min



笔记：
1. 队列就是简单的队列。主要是max_value();
2. max_value()如果时间复杂度为O(1)的话，需要维护一个双端队列。队首永远是下一个最大值。
假设队列内数据为
123454321
那么双端队列中只需要保证，head=5即可，等到5被弹出的时候，双端队列head=4；
如果这时插入6；
那双端队列就要一直从队尾弹出，一直弹到head=6

2022-10-22打卡

Offer 59 I        滑动窗口的最大值
Link：https://leetcode.cn/problems/hua ... de-zui-da-zhi-lcof/
题解：https://gitee.com/vincentmliu/Al ... DeZuiDaZhiLCOF.java
耗时： 1d


笔记：
1. 单调队列，如果窗口是[543216]，那么6之前的对Max都无贡献，队列top直接是6。
2. 往下滑动时，如果下个窗口是[432165],那么队列中应该保留6，5。因为6弹出后5可能是最大的。
3. 综上说明，滑动到nums[i]的时候，可以一直将队列前面的小于nums[i]的值都弹出去。如果遇到相等的，要保留。因为可能窗口是[543212345]，如果队列只有5，那么弹出去就报空了。所以此时队列应该是[5,5]。弹出第一个5之后，队列里面队首还是5

时间复杂度 O(n) 扫描一遍
空间复杂度 O(n) 需要一个栈来保存max值，最坏是O(n)