496. 下一个更大元素 I
原题链接：
https://leetcode.cn/problems/next-greater-element-i/description/
完成情况：
解题思路：
这两段代码实现了找出数组 nums1 中每个元素在数组 nums2 中的下一个更大元素，并将结果存储在数组中返回。
_496下一个更大元素I_单调栈
代码使用了栈和哈希表来实现。首先，将 nums1 中的每个元素和其下标存储在哈希表中。然后，遍历 nums2 数组，将元素的下标依次入栈。当遇到比栈顶元素大的元素时，不断弹出栈顶元素，并在哈希表中查找对应的下标，将其在结果数组中的位置更新为当前元素。最终返回结果数组。
_496下一个更大元素I_HashMap
代码也是用栈和哈希表来实现。首先，将 nums1 中的每个元素和其下标存储在哈希表中。然后，遍历 nums2 数组，将元素的下标依次入栈。当遇到比栈顶元素大的元素时，不断弹出栈顶元素，并在哈希表中查找对应的下标，将其在结果数组中的位置更新为当前元素。最终返回结果数组。
这两个版本的代码实现了相同的功能，只是在代码结构和变量命名上略有不同。第二个版本的代码更加简洁和易读。
参考代码：
_496下一个更大元素I_单调栈
package 代码随想录.动态规划;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
public class _496下一个更大元素I_单调栈 {
/**
* nums1[] 里面的元素，对应到 nums2[]的位置后，在nums2[]数组里 --> 比当前元素大的第一个元素的值
* @param nums1
* @param nums2
* @return
*/
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Deque<Integer> stack = new ArrayDeque<Integer>();
int [] result = new int[nums1.length];
Arrays.fill(result,-1);
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0;i< nums1.length;i++){
hashMap.put(nums1[i],i);
}
stack.add(0);
for (int i = 1;i < nums2.length;i++){
if (nums2[i] <= nums2[stack.peek()]){
stack.add(i);
}else {
while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]){
if (hashMap.containsKey(nums2[stack.peek()])){
Integer index = hashMap.get(nums2[stack.peek()]);
result[index] = nums2[i];
}
stack.pop();
}
stack.add(i);
}
}
return result;
}
}
_496下一个更大元素I_HashMap
package 代码随想录.动态规划;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;
public class _496下一个更大元素I_HashMap {
/**
*
* @param nums1
* @param nums2
* @return
*/
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < nums1.length; i++) {
map.put(nums1[i],i);
}
int result [] = new int[nums1.length];
Stack<Integer> tempStack = new Stack<Integer>();
Arrays.fill(result,-1);
for (int i = 0; i < nums2.length;i++){
while (!tempStack.isEmpty() && nums2[tempStack.peek()] < nums2[i]){
int preHead = nums2[tempStack.pop()];
if (map.containsKey(preHead)){
result[map.get(preHead)] = nums2[i];
}
}
tempStack.push(i);
}
return result;
}
}
错误经验吸取
在Java中，Stack类和Deque接口都可以用来实现栈的数据结构，但它们之间存在一些显著的区别：
类与接口：
Stack是一个基于Vector的扩展类，它实现了一个后进先出（LIFO）的栈。Deque是一个接口，代表双端队列（double-ended queue），它既可以作为栈使用（后进先出），也可以作为队列使用（先进先出）。
历史和现代性：
Stack类是Java早期版本提供的，随后在Java中被认为是一种遗留的类，因为它有几个问题，包括效率不高和不推荐扩展。Deque接口则是Java集合框架（Java Collections Framework）的一部分，是在Java 6中引入的，表示了一种更现代和更灵活的数据结构。
功能：
Stack仅提供了标准的栈操作，如pop()、push()、peek()、empty()和search()。Deque接口除了支持栈操作之外（通过addFirst()、removeFirst()等方法），还支持队列操作，如addLast()、removeLast()等，并且提供了更多的方法来在两端插入、移除和检查元素。
性能：
Stack继承于Vector，意味着它是线程安全的，但线程安全通常带来不必要的性能开销，因为大多数使用栈的情况都不需要线程安全。Deque实现，比如ArrayDeque和LinkedList，通常会更快，因为它们不是线程安全的，并且在非线程安全的环境下工作得更高效。
推荐使用：
- 官方文档建议使用
Deque接口来实现栈，其推荐的实现类是ArrayDeque。它更快，使用起来更加灵活，并且提供了更为丰富的API。
- 官方文档建议使用
总的来说，即使Stack和Deque都可以实现栈的功能，但通常推荐使用Deque接口的实现，如ArrayDeque，来获取更好的性能和更大的灵活性。
Deque与Stack的区别
在Java中，Stack类的add方法和Deque接口的add方法在功能上有些细微的区别，主要是因为它们底层继承和实现的数据结构不同。
Stack类的add方法:
Stack类继承自Vector类，所以Stack的add方法实际上是Vector的方法。add(E element)：将元素添加到Vector的末尾，这也就是Stack的末尾。因为Stack是后进先出（LIFO）的数据结构，所以这个操作并不遵守栈的原则。换句话说，使用add方法添加的元素并不保证在下一个pop调用时被移除。
Deque接口的add方法:
Deque代表双端队列。实现Deque接口的类，如ArrayDeque和LinkedList，拥有两个添加元素的方法：addFirst(E e)和addLast(E e)，分别在双端队列的前面和后面添加元素。add(E element)：在双端队列的末尾添加元素，这相等于使用addLast(E e)，当用作栈时，这与栈的行为不一致，因为栈应当是后进先出的。- 当
Deque用作栈时，正常情况下不会使用add方法来添加元素，而是使用push(E e)，这样新添加的元素会放在双端队列的开头（栈顶），遵循栈的后进先出原则。
在实际使用中，为了维持栈的性质（后进先出），当我们使用Deque来实现栈时，推荐使用push(E e)方法，而不是add(E e)。而Stack类的add方法通常不用于典型的栈操作，因为它不遵循栈的后进先出原则，除非你出于某种特殊目的需要这么做。
