单调栈问题---(每日温度,下一个更大元素Ⅰ)

代码随想录day 58 单调栈问题— 每日温度,下一个更大元素Ⅰ

1.leetcode 739. 每日温度

1.1 详细思路及解题步骤

  这题会用到单调栈的方法来做，为什么用单调栈呢，什么时候又能想到用单调栈呢?
  当题目出现一维数组且需要求当前位置往前或者往后的第一个比它大or小的值，这时候就会用单调栈的方法去做。
  需要考虑的问题有

1. 单调栈中存放的是索引
2. 单调栈中存放的顺序，是递增还是递减呢。

使用单调栈主要有三个判断条件。

当前遍历的元素T[i]小于栈顶元素T[st.peek()]的情况 //栈.peek()在Java中表示栈顶元素
当前遍历的元素T[i]等于栈顶元素T[st.peek()]的情况
当前遍历的元素T[i]大于栈顶元素T[st.peek()]的情况

以第一个例子 temp = [73,74,75,71,69,72,76,73]

1. 先将第一个索引也就是0方法栈中
2. 然后遍历到第二个位置的时候判断temp[1]>temp[stack.peek()]/表示栈顶元素/
   这时就找到了比temp[0]大的值，然后就用res[0]=1-stack.peek().
   …
   …上面是当前遍历的元素T[i]大于栈顶元素T[st.peek()]的情况 如果当前遍历的元素T[i]小于栈顶元素T[st.peek()]的情况 和当前遍历的元素T[i]等于栈顶元素T[st.peek()]的时候，那么就直接将遍历位置的索引存入栈中stack.push(i),就按照这种方法顺着来就欧克了。

1.2Java版代码示例

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
      int len=temperatures.length;
      int[] result= new int[len];
      Deque<Integer> stack=new LinkedList<>();
      stack.push(0);
      for(int i=1;i<len;i++){
          if(temperatures[i]<=temperatures[stack.peek()]){
              stack.push(i);
          }else{
            while(!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
              result[stack.peek()]=i-stack.peek();
              stack.pop();
          }
          stack.push(i);//别漏了，弹出来之后最终要加进去
          }

      } 
      return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.leetcode 496. 下一个更大元素 I

---

2.1 详细思路及解题步骤

  这题与上题做法差不多，但是会比较难想，可以先将nums1的内容存放在一个Map上面，数组的值和索引一一对应，然后就开始对nums2进行放入栈的操作，
①当前遍历的元素nums2[i]小于栈顶元素nums2[st.peek()]和 当前遍历的元素nums2[i]等于栈顶元素nums2[st.peek()]的情况 就不用考虑nums1中的东西.
②当前遍历的元素nums2[i]大于栈顶元素T[st.peek()]的情况时候，就需要考虑栈顶的元素是否在Map中存在，如果存在就需要记录当前遍历的nums[2]，此时这个值就是要求的更大的下个元素。

2.2Java版代码示例

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
       Deque<Integer> stack=new LinkedList<>();
       int[] result=new int[nums1.length];
       Arrays.fill(result,-1);
       Map<Integer,Integer> map=new HashMap<>();
       stack.push(0);
       for(int i=0;i<nums1.length;i++){
           map.put(nums1[i],i);
       }
       for(int i=1;i<nums2.length;i++){
           if(nums2[stack.peek()]>=nums2[i]){
               stack.push(i);
           }else{
               while(!stack.isEmpty()&&nums2[stack.peek()]<nums2[i]){
                   if(map.containsKey(nums2[stack.peek()])){
                       Integer in=map.get(nums2[stack.peek()]);
                       result[in]=nums2[i];
                   }
                   stack.pop();//别漏勒
               }
               stack.push(i);
           }
       }
       return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27