单调栈

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]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]
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
// 从右往左
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];           // 1. 结果数组，默认值为0
        Deque<Integer> st = new ArrayDeque<>(); // 2. 栈，存储下标
        
        // 3. 从最后一天开始向左遍历
        for (int i = n - 1; i >= 0; i--) {
            int t = temperatures[i];
            
            // 4. 关键：维护栈的单调递减性
            // 只要栈顶温度 <= 当前温度，就弹出栈顶
            // 因为这些栈顶温度既比当前低，又在当前右边，对更左边的天来说毫无意义
            while (!st.isEmpty() && t >= temperatures[st.peek()]) {
                st.pop();
            }
            
            // 5. 经过上面的清理后，如果栈非空，
            // 则栈顶元素就是右边第一个比当前温度更高的温度下标
            if (!st.isEmpty()) {
                ans[i] = st.peek() - i;
            }
            // 如果栈空，说明右边没有更高温度，ans[i]保持为0
            
            // 6. 将当前索引入栈，作为未来左边天的“候选答案”
            st.push(i);
        }
        return ans;
    }
}

步骤图解

用 temperatures = [73,74,75,71,69,72,76,73] 来模拟：

i (从右向左) t 栈中下标(温度) 比较与弹出 操作后 ans[i] 入栈后状态
7 (73) 73 空 - 0 [7(73)]
6 (76) 76 [7(73)] 76 >= 73，弹出7 0 [6(76)]
5 (72) 72 [6(76)] 72 >= 76? 否 6-5 = 1 [6(76), 5(72)]
4 (69) 69 [6(76), 5(72)] 69 >= 72? 否 5-4 = 1 [6(76), 5(72), 4(69)]
3 (71) 71 [..., 4(69)] 71 >= 69? 是，弹出4。现在栈顶是5(72)，71 >= 72? 否 5-3 = 2 [6(76), 5(72), 3(71)]
2 (75) 75 [..., 3(71)] 75 >= 71? 是，弹出3。栈顶5(72)，75 >= 72? 是，弹出5。栈顶6(76)，75 >= 76? 否 6-2 = 4 [6(76), 2(75)]
1 (74) 74 [6(76), 2(75)] 74 >= 75? 否 2-1 = 1 [6(76), 2(75), 1(74)]
0 (73) 73 [..., 1(74)] 73 >= 74? 否 1-0 = 1 [6(76), 2(75), 1(74), 0(73)]

现在结果是 [1, 1, 4, 2, 1, 1, 0, 0]，与示例完全一致。

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
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
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 1. 构建哈希表，记录 nums1 中每个元素及其下标
        int n = nums1.length;
        Map<Integer, Integer> idx = new HashMap<>(n, 1); // 预分配空间，提升效率
        for (int i = 0; i < n; i++) {
            idx.put(nums1[i], i);
        }

        int[] ans = new int[n];
        Arrays.fill(ans, -1); // 默认值设为 -1，处理找不到更大元素的情况
        Deque<Integer> st = new ArrayDeque<>(); // 使用 ArrayDeque 作为栈

        // 2. 从右向左遍历 nums2
        for (int i = nums2.length - 1; i >= 0; i--) {
            int x = nums2[i];
            
            // 3. 维护单调栈：弹出所有小于等于 x 的栈顶元素
            while (!st.isEmpty() && x >= st.peek()) {
                st.pop();
            }
            
            // 4. 如果 x 在 nums1 中，并且栈不为空，则栈顶元素就是 x 的下一个更大元素
            if (!st.isEmpty() && idx.containsKey(x)) {
                ans[idx.get(x)] = st.peek();
            }
            
            // 5. 将当前元素 x 入栈，作为左边元素的候选
            st.push(x);
        }
        return ans;
    }
}

步骤图解

为了更直观，我们用 nums1 = [4,1,2], nums2 = [1,3,4,2] 来模拟过程：

步骤 i x 栈操作 x 在 nums1 中？ 动作
1 3 2 栈空，入栈 → [2] ✅ 是 栈空，不记录
2 2 4 4 >= 2，弹出 2 → 栈空，入栈 → [4] ✅ 是 栈空，不记录
3 1 3 3 >= 4? 否，入栈 → [4, 3] ❌ 否 不记录
4 0 1 1 >= 3? 否，入栈 → [4, 3, 1] ✅ 是 栈顶 3 存在，记录 ans[1] = 3

最终 ans = [-1, 3, -1] ✅（正确）

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 2 * n - 1; i >= 0; i--) {
            int x = nums[i % n];
            while (!st.isEmpty() && x >= st.peek()) {
                // 由于 x 的出现，栈顶元素永远不会是左边元素的「下一个更大元素」
                st.pop();
            }
            if (i < n && !st.isEmpty()) {
                ans[i] = st.peek();
            }
            st.push(x);
        }
        return ans;
    }
}

步骤图解

i (从右向左) x = nums[i%3] 栈中元素（值） 比较与弹出 是否记录答案 操作后 ans[i%3] 入栈后状态
5 nums[2] = 1 空 - ❌ (i≥n) - [1]
4 nums[1] = 2 [1] 2 >= 1? 是，弹出1 ❌ (i≥n) - [2]
3 nums[0] = 1 [2] 1 >= 2? 否 ❌ (i≥n) - [2, 1]
2 nums[2] = 1 [2, 1] 1 >= 1? 是，弹出1；现在栈顶2，1 >= 2? 否 ✅ (i<n) ans[2] = 2 [2, 1]
1 nums[1] = 2 [2, 1] 2 >= 1? 是，弹出1；现在栈顶2，2 >= 2? 是，弹出2；栈空 ✅ (i<n) ans[1] = -1（栈空） [2]
0 nums[0] = 1 [2] 1 >= 2? 否 ✅ (i<n) ans[0] = 2 [2, 1]

难题暂缓

42. 接雨水

84. 柱状图中最大的矩形

图论

图论统一使用ACM模式，ACM模式需要接收输入参数

本文只是用邻接矩阵的写法

可达路径

题目描述

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入描述

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输出描述

输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5 ， 5后面没有空格！

输入示例

1
2
3
4
5
6
5 5
1 3
3 5
1 2
2 4
4 5

输出示例

1
2
1 3 5
1 2 4 5

提示信息

img

用例解释：

有五个节点，其中的从 1 到达 5 的路径有两个，分别是 1 -> 3 -> 5 和 1 -> 2 -> 4 -> 5。

因为拥有多条路径，所以输出结果为：

1 3 5
1 2 4 5

或

1 2 4 5
1 3 5
都算正确。

数据范围：

  • 图中不存在自环
  • 图中不存在平行边
  • 1 <= N <= 100
  • 1 <= M <= 500
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
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径
    static List<Integer> path = new ArrayList<>(); // 1节点到终点的路径

    public static void dfs(int[][] graph, int x, int n) {
        // 当前遍历的节点x 到达节点n
        if (x == n) { // 找到符合条件的一条路径
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
            if (graph[x][i] == 1) { // 找到 x链接的节点
                path.add(i); // 遍历到的节点加入到路径中来
                dfs(graph, i, n); // 进入下一层递归
                path.remove(path.size() - 1); // 回溯，撤销本节点
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 节点编号从1到n，所以申请 n+1 这么大的数组
        int[][] graph = new int[n + 1][n + 1];

        for (int i = 0; i < m; i++) {
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            // 使用邻接矩阵表示无向图，1 表示 s 与 t 是相连的
            graph[s][t] = 1;
        }

        path.add(1); // 无论什么路径已经是从1节点出发
        dfs(graph, 1, n); // 开始遍历

        // 输出结果
        if (result.isEmpty()) System.out.println(-1);
        for (List<Integer> pa : result) {
            for (int i = 0; i < pa.size() - 1; i++) {
                System.out.print(pa.get(i) + " ");
            }
            System.out.println(pa.get(pa.size() - 1));
        }
    }
}

其他

不涉及到之前列出的其他方法，属于新思路

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

1
2
3
4
5
6
7
8
9
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
    	int ans = 0;      // 最终答案：候选起点
    	int minS = 0;     // 记录遍历过程中，油量最低时的值
    	int s = 0;        // 当前油量（从假设的起点0开始累积）
	
    	for (int i = 0; i < gas.length; i++) {
    	    s += gas[i] - cost[i]; // 在i站加油，开到i+1站后的净油量变化
    	    
    	    if (s < minS) {        // 发现了一个新的油量“历史最低点”
    	        minS = s;          // 更新最低油量记录
    	        ans = i + 1;       // 关键：最低点的下一个位置，就是最佳候选起点
    	    }
    	}
    	// 循环结束后，s 就是总净油量（gas总和 - cost总和）
    	return s < 0 ? -1 : ans;
	}
}