day58| 739. 每日温度、496.下一个更大元素 I

一、739. 每日温度

注意的点：

1. 栈中存放的下标，而不是原数组的元素值。
2. 栈维持的一个递减的序列（从栈底到栈顶），目的是当发现一个比较大的值出现时，可以找出原数组的相对位置，而不会丢失位置信息。
3. 要一直看栈顶元素的对应值是否小于当前入栈元素的对应值，所以使用 while 而不是 if
4. 要注意，比较的是以栈顶元素为下标的原数组元素值，而并非栈顶元素。
5. 注意，每个位置的元素都会有一个入栈的操作。

以下是代码部分：

	//单调栈
    public int[] dailyTemperatures(int[] temperatures) {

        Stack<Integer> s = new Stack<>();

        int[] result = new int[temperatures.length];

        //思路：在栈中维持一个递减的序列（从栈底到栈顶）
        for (int i = 0; i < temperatures.length; i++) {

            //要一直看栈顶元素是否小于当前入栈元素，所以使用 while 而不是 if

            //踩坑：temperatures[i] > s.peek()  ——>    这里不是>s.peek(),而是>temp[s.peek()]
            while (!s.isEmpty() && temperatures[i] > temperatures[s.peek()]){
                //这里要减s.peek，因为是求之间的距离
                result[s.peek()] = i - s.peek();
                s.pop();
            }
            //同时，还要进行一个入栈操作
            s.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

二、496.下一个更大元素 I

注意的点：

1. 由于看到标记的是“简单”题，所以尝试使用了暴力破解法，结果真的可以通过。就是中间踩了一些坑。
2. 使用单调栈的方式的话，相较于前一题，多了一个匹配的工序——计算出nums2数组的每个位置的值后，还要看该位置的元素是否也属于nums1，若是，则依据map哈希表给对应的result下标赋值，否则，不做处理。

以下是代码部分：

public class 下一个更大元素I496 {

    //暴力循环破解
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        int[] result = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {


            for (int j = 0; j < nums2.length; j++) {

                while (j < nums2.length && nums1[i] != nums2[j])
                    j++;

                if(j == nums2.length)
                    break;

                //这里迭代寻找第一个大于该值的数
                while (j < nums2.length && nums1[i] >= nums2[j]){
                    j++;
                }

                if(j == nums2.length)
                    break;

                //如果符合条件，即找到一个大的值，则返回该值
                if(nums1[i] < nums2[j]) {
                    result[i] = nums2[j];
                    break;
                }
            }

            //判断如果result为0，即没有被赋值，则置为-1
            if(result[i] == 0)
                result[i] = -1;
        }

        return result;
    }

    //单调栈方式
    //思路：其实就是在nums2中找右边第一个最大值，然后再看nums2中的元素是否在nums1中也存在
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {

        int[] result = new int[nums1.length];
        //要先全部初始化为-1
        for (int i = 0; i < result.length; i++) {
            result[i] = -1;
        }

        Map<Integer,Integer> map = new HashMap<>();
        //这里map的value对应的是下标，这样好在result中进行对应的赋值
        for (int i = 0; i < result.length; i++) {
            map.put(nums1[i], i);
        }

        Stack<Integer> s = new Stack<>();

        //对nums2进行右边最大值的查找
        for (int i = 0; i < nums2.length; i++) {

            while (!s.isEmpty() && nums2[s.peek()] < nums2[i]){

                //这里要进行查找、并赋值
                if(map.containsKey(nums2[s.peek()]))
                    result[map.get(nums2[s.peek()])] = nums2[i];

                //弹出栈顶元素
                s.pop();
            }

            //入栈
            s.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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79