单调栈No.1739.每日温度. - 力扣LeetCode给定一个整数数组temperatures表示每天的温度返回一个数组answer其中answer[i]是指对于第i天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用0来代替。示例 1:输入:temperatures [73,74,75,71,69,72,76,73]输出:[1,1,4,2,1,1,0,0]示例 2:输入:temperatures [30,40,50,60]输出:[1,1,1,0]示例 3:输入:temperatures [30,60,90]输出:[1,1,0]提示1 temperatures.length 10530 temperatures[i] 100class Solution { public int[] dailyTemperatures(int[] temperatures) { // 获取温度数组的长度 int len temperatures.length; // 用来存储结果数组每个元素存储第 i 天后有几天温度升高 int[] ans new int[len]; // 创建一个栈用于存储索引。栈中的元素代表温度尚未找到升高天数的索引 DequeInteger stk new ArrayDeque(); // 遍历温度数组 for (int i 0; i len; i) { int t temperatures[i]; // 当前的温度 // 当栈不为空且当前温度比栈顶所记录的索引的温度高时进入循环 while (!stk.isEmpty() t temperatures[stk.peek()]) { // 栈顶的索引所对应的温度小于当前温度所以弹出栈顶元素 int j stk.pop(); // 计算当前温度超过之前温度的间隔天数 ans[j] i - j; } // 当前温度的索引入栈等待后续更高温度的判断 stk.push(i); } // 返回结果数组表示每一天距离下一个温度升高的天数 return ans; } }ans[j]的含义j是从栈中弹出的某一天的索引这一天的温度较低现在找到了比它温度更高的那一天i。我们要填充的是第j天的答案即ans[j]应该等于i - j表示从第j天到第i天经历的天数。关键点i是比j天温度更高的那一天j是温度较低并等待找到更高温度的那一天。你要更新的是第j天的答案所以我们写ans[j]。ans[j] i - j意思是第j天之后温度升高的天数是从i天到j天之间的天数差i - j。ArrayList基于动态数组的实现随机访问和遍历性能优越。适合频繁查询元素的场景。LinkedList基于双向链表的实现适合频繁插入和删除操作特别是头部和尾部的操作。实现了Deque接口也可用作栈或队列。ArrayDeque头部和尾部的插入和删除操作平均时间复杂度为 O(1)。随机访问元素不支持通过索引随机访问必须通过迭代遍历时间复杂度为 O(n)。ArrayList随机访问元素通过索引直接访问元素时间复杂度为 O(1)。尾部插入或删除元素平均时间复杂度为 O(1)。头部或中间插入和删除元素由于需要移动其他元素时间复杂度为 O(n)。3.线程安全性ArrayDeque和ArrayList都不是线程安全的。如果在多线程环境下使用它们需要手动同步操作。4.扩容机制ArrayDeque和ArrayList都是基于动态数组实现的。随着元素的增加它们都会自动扩容通常是当前容量的1.5倍或2倍。但是扩容时性能会下降因为需要重新分配更大的数组并复制已有元素。5.使用限制ArrayDeque不允许存储null值。任何null元素的插入都会抛出NullPointerException。更适合用作栈或队列。ArrayList允许存储null值null可以被视为一个有效的元素。6.总结如果你需要双端操作即从头部和尾部都可以高效插入和删除的数据结构使用ArrayDeque。如果你需要随机访问元素并且主要是在尾部操作元素使用ArrayList。代码示例ArrayDeque用作栈ArrayDequeInteger stack new ArrayDeque(); stack.push(1); // 入栈 stack.push(2); stack.push(3); System.out.println(stack.pop()); // 出栈, 输出3ArrayList用作列表ArrayListInteger list new ArrayList(); list.add(1); // 尾部添加 list.add(2); list.add(3); System.out.println(list.get(0)); // 随机访问, 输出1No.2962.最大宽度坡. - 力扣LeetCode给定一个整数数组A坡是元组(i, j)其中i j且A[i] A[j]。这样的坡的宽度为j - i。找出A中的坡的最大宽度如果不存在返回 0 。示例 1输入[6,0,8,2,1,5]输出4解释最大宽度的坡为 (i, j) (1, 5): A[1] 0 且 A[5] 5.示例 2输入[9,8,1,0,1,9,4,0,4,1]输出7解释最大宽度的坡为 (i, j) (2, 9): A[2] 1 且 A[9] 1.提示2 A.length 500000 A[i] 50000public class MaxWidthRamp { public int maxWidthRamp(int[] A) { StackInteger stack new Stack(); int n A.length; // 第一次遍历数组构建单调递减栈 for (int i 0; i n; i) { // 检查栈是否为空或者当前元素值小于栈顶元素对应的值 if (stack.isEmpty() || A[stack.peek()] A[i]) { stack.push(i); // 将当前元素索引入栈 } } int maxWidth 0; // 第二次从右到左遍历寻找最大宽度坡度 for (int j n - 1; j 0; j--) { // 当栈不为空且当前元素值大于或等于栈顶元素值时计算坡度宽度 while (!stack.isEmpty() A[stack.peek()] A[j]) { maxWidth Math.max(maxWidth, j - stack.pop()); } } return maxWidth; } public static void main(String[] args) { MaxWidthRamp solution new MaxWidthRamp(); int[] A {6, 0, 8, 2, 1, 5}; System.out.println(solution.maxWidthRamp(A)); // 输出4 } }