网站建设公司 销量,有哪些做设计交易网站,弋阳县建设工程网站,商家在携程旅游网站怎样做宣传题库链接#xff1a;https://leetcode.cn/problem-list/e8X3pBZi/ 类型题目解决方案栈的应用剑指 Offer II 036. 后缀表达式模拟 栈 ⭐剑指 Offer II 037. 小行星碰撞分类讨论 栈 ⭐单调栈剑指 Offer II 038. 每日温度单调栈 ⭐剑指 Offer II 039. 直方图最大矩形面积单调栈…题库链接https://leetcode.cn/problem-list/e8X3pBZi/ 类型题目解决方案栈的应用剑指 Offer II 036. 后缀表达式模拟 栈 ⭐剑指 Offer II 037. 小行星碰撞分类讨论 栈 ⭐单调栈剑指 Offer II 038. 每日温度单调栈 ⭐剑指 Offer II 039. 直方图最大矩形面积单调栈 ⭐剑指 Offer II 040. 矩阵中的最大矩形矩阵转化直方图 单调栈 ⭐ 栈后入后出所以栈的插入和删除操作都发生在栈顶 Java 中 Stack 的常用操作 push(e)元素 e 入栈pop()位于栈顶的元素出栈并返回该元素peek()返回位于栈顶的元素该元素不出栈 1. 剑指 Offer II 036. 后缀表达式 – P93 根据 逆波兰表示法求该后缀表达式的计算结果。 有效的算符包括 、-、*、/ 。每个运算对象可以是整数也可以是另一个逆波兰表达式。 1.1 模拟 栈 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) 注意该题是通过栈来保存操作数但不保存运算符通过对运算符的判断从而进行数值的模拟计算。 class Solution {// Solution1用栈存储每当遇到运算符时就从栈中弹出两个数进行计算后存入// Note栈中只保存操作数不保存运算符public int evalRPN(String[] tokens) {ArrayDequeInteger deque new ArrayDeque();for (String token : tokens) {switch(token) {case :case -:case *:case /:int num1 deque.pop();int num2 deque.pop();deque.push(caculate(num1, num2, token));break;default: // 不是运算符则入栈deque.push(Integer.parseInt(token));}}return deque.poll(); // 最后栈中只剩下最终结果}public int caculate(int a, int b, String operator) {switch(operator) {case :return a b;case -:return b - a;case *:return b * a;case /:return b / a;default:return 0;}}
}2. 剑指 Offer II 037. 小行星碰撞 – P96 给定一个整数数组 asteroids表示在同一行的小行星。 对于数组中的每一个元素其绝对值表示小行星的大小正负表示小行星的移动方向正表示向右移动负表示向左移动。每一颗小行星以相同的速度移动。 找出碰撞后剩下的所有小行星。碰撞规则两个行星相互碰撞较小的行星会爆炸。如果两颗行星大小相同则两颗行星都会爆炸。两颗移动方向相同的行星永远不会发生碰撞。 2.1 分类讨论 栈 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
class Solution {public int[] asteroidCollision(int[] asteroids) {ArrayDequeInteger deque new ArrayDeque();for (int as : asteroids) {// 1. 栈非空相向碰撞保留大值while (!deque.isEmpty() deque.peek() 0 deque.peek() -as) {deque.pop();}// 2. 栈非空相向碰撞同归于尽if (!deque.isEmpty() as 0 deque.peek() -as) {deque.pop();}// 3. 同向 | 栈为空 则入栈else if (as 0 || deque.isEmpty() || deque.peek() 0) {deque.push(as);}}int[] res new int[deque.size()];for (int i res.length-1; i 0; i--) {res[i] deque.pop();}return res;}
}3. 剑指 Offer II 038. 每日温度 – P98 请根据每日 气温 列表 temperatures 重新生成一个列表要求其对应位置的输出为要想观测到更高的气温至少需要等待的天数。如果气温在这之后都不会升高请在该位置用 0 来代替。 3.1 单调栈 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) 关于单调栈的更多内容可参考【华为机考】专题突破 第一周单调栈 739 、503 、901、84 …… 该题解中的栈存储的是元素的 下标。 class Solution {// Solution1单调栈public int[] dailyTemperatures(int[] temperatures) {int[] res new int[temperatures.length];StackInteger sk new Stack();for (int i 0; i temperatures.length; i) {// 如果栈非空且当前气温大于栈顶气温则计算等待天数并弹出栈顶元素while (!sk.empty() temperatures[i] temperatures[sk.peek()]) {int index sk.pop();res[index] i - index; }// 顺序添加每个元素不存在更大气温的元素会被永远存在栈中sk.push(i);}return res;}
}4. 剑指 Offer II 039. 直方图最大矩形面积 – P100 给定非负整数数组 heights 数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。 求在该柱状图中能够勾勒出来的矩形的最大面积。 4.1 单调栈 – O(n)⭐
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n) Key每次计算的是某某高度下的矩形的最大面积。高为出栈元素高度宽则为比该出栈元素小的两侧元素下标的差值。 class Solution {// Solution1单调递增栈栈中存储元素下标public int largestRectangleArea(int[] heights) {StackInteger sk new Stack();sk.push(-1); // 初始下标int max 0;for (int i 0; i heights.length; i) {// 如果当前元素小于或等于栈顶元素则让栈顶元素出栈同时计算栈顶高度矩形的最大面积while (sk.peek() ! -1 heights[sk.peek()] heights[i]) {int h heights[sk.pop()];int w i - sk.peek() - 1;max Math.max(max, h * w);}// 栈中元素始终保持单调递增sk.push(i);}while (sk.peek() ! -1) { // 计算栈中剩余元素高度矩形的最大面积int h heights[sk.pop()];int w heights.length - sk.peek() -1;max Math.max(max, h * w);}return max;}
}4.2 分治 – O(logn)
时间复杂度 O ( l o g n ) O(logn) O(logn)空间复杂度 O ( n ) O(n) O(n) Key将直方图的最大矩形分成了3种可能1. 矩形通过最矮的柱子2. 矩形的起始柱子和终止柱子都在最矮的柱子的左侧3. 矩形的起始柱子和终止柱子都在最矮的柱子的右侧。 class Solution {// Solution2分治法// 每次找最小的元素为中点然后向左右两侧递归public int largestRectangleArea(int[] heights) {return helper(heights, 0, heights.length);}public int helper(int[] heights, int l, int r) {if (l r) return 0;if (l1 r) return heights[l];int minIndex l;for (int i l1; i r; i) {minIndex heights[i] heights[minIndex] ? i : minIndex;}int max (r - l) * heights[minIndex];int left helper(heights, l, minIndex);int right helper(heights, minIndex1, r);max Math.max(max, left);return Math.max(max, right);}
}5. 剑指 Offer II 040. 矩阵中的最大矩形 – P106
5.1 矩阵转直方图 单调栈 – O(mn)⭐
时间复杂度 O ( m n ) O(mn) O(mn)空间复杂度 O ( n ) O(n) O(n) Key要有抽象思维将矩阵01矩阵抽象成直方图求1所能构成矩形的最大面积进而套用上一题的代码求解直方图的最大面积。 class Solution {// Solution1将矩阵转化成直方图求直方图的最大面积public int maximalRectangle(String[] matrix) {if (matrix.length 0) return 0;char[][] str new char[matrix.length][];for (int i 0; i matrix.length; i) {str[i] matrix[i].toCharArray();}int[] heights new int[str[0].length];int res 0;for (char[] row : str) {for (int i 0; i row.length; i) {if (row[i] 0) {heights[i] 0;} else {heights[i];} }res Math.max(res, caculateArea(heights));}return res;}public int caculateArea(int[] heights) {StackInteger sk new Stack();sk.push(-1);int max 0;for (int i 0; i heights.length; i) {while (sk.peek() ! -1 heights[sk.peek()] heights[i]) {int h heights[sk.pop()];int w i - sk.peek() - 1;max Math.max(max, h * w);}sk.push(i);}while (sk.peek() ! -1) {int h heights[sk.pop()];int w heights.length - sk.peek() - 1;max Math.max(max, h * w);}return max;}
}6. 继续提升加练题目 可参考 栈 · SharingSource/LogicStack-LeetCode Wiki · GitHub单调栈 · SharingSource/LogicStack-LeetCode Wiki · GitHub
