要寻找任一个元素的 右边或者左边第一个比自己大或者小的元素的位置 ，此时我们就要想到可以用单调栈了。

时间复杂度 $O(n)$

  • 单调栈里存放的是下标 $i$

  • 以右边第一个比自己大的元素为例，需要维护一个从 栈顶到栈底 递增 的栈

  • 使用单调栈主要有三个判断条件（以右边第一个比自己大的元素为例）

    • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
      • i入栈
    • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
      • i入栈， 因为是大于，不用记录
    • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
      • 弹出栈顶元素st.top()，i压栈，记录 res[st.top]与i的关系

    739. 每日温度⁍

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

思路

找右边第一个比temp[i]大的元素的坐标j

ans[i] = j-i

维护栈顶到栈底递增单调栈

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
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new LinkedList<>();
        int[] ans = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
            }else{
                int temp = temperatures[i];
                int top = stack.peek();
                // 不断和栈顶元素比较，直到不比栈顶元素大
                while (temp > temperatures[top]) {
                    top = stack.pop();
                    ans[top] = i-top;
                    // 如果栈空，也跳出循环
                    if (stack.isEmpty()) {
                        break;
                    }
                    top = stack.peek();
                }
                stack.push(i);
            }
        }
        return ans;
    }
}

参考，中间的循环更简单的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int[] dailyTemperatures(int[] temperatures) {
    Stack<Integer> stack = new Stack<>();
    int[] res = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
        /**
         * 取出下标进行元素值的比较
         */
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int preIndex = stack.pop();
            res[preIndex] = i - preIndex;
        }
        /**
         * 注意 放入的是元素位置
         */
        stack.push(i);
    }
    return res;
}

496. 下一个更大的元素i⁍

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

1
2
3
4
5
6
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

示例 2：

1
2
3
4
5
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。

提示：

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中

**进阶：**你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？

思路

先遍历nums2，找到每个值对应的下一个元素，并用哈希表记录

再遍历nums2，按顺序将每个值的下一个元素添加到结果中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> stack = new LinkedList<>();
        // 记录nums2中的元素x的下一个更大元素
        Map<Integer,Integer> map = new HashMap<>();
        int[] res = new int[nums1.length];

        // 先遍历nums2，找到每个元素的下一个更大元素
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i]>nums2[stack.peek()]) {
                int top = stack.pop();
                map.put(nums2[top],nums2[i]);
            }
            stack.push(i);
        }

        for (int i = 0; i < nums1.length; i++) {
            int n = map.getOrDefault(nums1[i],-1); // 不存在则置-1
            res[i] = n;
        }
        return res;
    }
}

503.下一个更大元素II⁍

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

1
2
3
4
5
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

示例 2:

1
2
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

  • 1 <= nums.length <= 10^4
  • -109 <= nums[i] <= 10^9

思路：

最多循环一轮，所以循环到2n结束，算坐标的时候mod n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        int n = nums.length;
        int res[] = new int[n];
        Arrays.fill(res,-1);
        for (int i = 0; i < 2*n; i++) { // 设为2*n即可
            int j = i%n;
            while (!stack.isEmpty()&&nums[j]> nums[stack.peek()]){
                int top = stack.pop();
                res[top] = nums[j];
            }
            stack.push(j);
        }
        return res;
    }
}