力扣刷题单调栈

本文主要是介绍力扣刷题单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

单调栈

No.1

739.每日温度. - 力扣（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 <= 105
• 30 <= temperatures[i] <= 100

class Solution {public int[] dailyTemperatures(int[] temperatures) {// 获取温度数组的长度int len = temperatures.length;// 用来存储结果数组，每个元素存储第 i 天后有几天温度升高int[] ans = new int[len];  // 创建一个栈用于存储索引。栈中的元素代表温度尚未找到升高天数的索引Deque<Integer> 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 用作栈：

  ArrayDeque<Integer> stack = new ArrayDeque<>();
  stack.push(1);  // 入栈
  stack.push(2);
  stack.push(3);
  System.out.println(stack.pop());  // 出栈, 输出3
  

• ArrayList 用作列表：

ArrayList<Integer> list = new ArrayList<>();
list.add(1);  // 尾部添加
list.add(2);
list.add(3);
System.out.println(list.get(0));  // 随机访问, 输出1

 

这篇关于力扣刷题单调栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---