【LeetCode每日一题合集】2023.12.11-2023.12.17 （⭐二维前缀和+二维差分 珂朵莉树）

1631. 最小体力消耗路径⭐🐂

https://leetcode.cn/problems/path-with-minimum-effort/description/?envType=daily-question&envId=2023-12-11

提示：

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

解法1——二分查找

二分查找答案，每次用 BFS 检查是否合理。
时间复杂度是 $mnlogC$

class Solution {int m, n;int[][] heights;int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};public int minimumEffortPath(int[][] heights) {m = heights.length;n = heights[0].length;this.heights = heights;int l = 0, r = 999999;while (l < r) {int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;}public boolean check (int mx) {Queue<int[]> q = new LinkedList<>();boolean[][] st = new boolean[m][n];st[0][0] = true;q.offer(new int[]{0, 0});while (!q.isEmpty()) {int[] cur = q.poll();int x = cur[0], y = cur[1];if (x == m - 1 && y == n - 1) return true;for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && !st[nx][ny] && Math.abs(heights[x][y] - heights[nx][ny]) <= mx) {q.offer(new int[]{nx, ny});st[nx][ny] = true;}}}return false;}
}

解法2——并查集

【算法基础：数据结构】2.3 并查集

把数据当作一个图，将所有边放入列表并从小到大排序，之后逐个枚举边，将两边的点放入并查集中，直到起点和终点位于同一个集合，此时的边就是答案。

class Solution {int[] p;public int minimumEffortPath(int[][] heights) {int m = heights.length, n = heights[0].length;List<int[]> edges = new ArrayList<>();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {int id = i * n + j;if (i > 0) {// 把这个点和上面的点这条边放进去edges.add(new int[]{id - n, id, Math.abs(heights[i][j] - heights[i - 1][j])});}if (j > 0) {// 把这个点和左面的点这条边放进去edges.add(new int[]{id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])});}}}Collections.sort(edges, (x, y) -> {return x[2] - y[2];});p = new int[m * n];Arrays.setAll(p, e -> e);int ans = 0;// 从小到大枚举每个边for (int[] edge: edges) {int x = edge[0], y = edge[1], v = edge[2];p[find(x)] = find(y);if (find(0) == find(m * n - 1)) {		// 加入这个边之后，0和m*n-1联通了ans = v;break;}}return ans;}public int find(int x) {if (x != p[x]) p[x] = find(p[x]);return p[x];}
}

解法3——最短路 Dijkstra

【算法基础：搜索与图论】3.4 求最短路算法（Dijkstra&bellman-ford&spfa&Floyd）

使用堆优化的 Dijkstra 算法。

class Solution {int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};public int minimumEffortPath(int[][] heights) {int m = heights.length, n = heights[0].length;PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {return x[2] - y[2];});pq.offer(new int[]{0, 0, 0});int[][] dist = new int[m][n];for (int i = 0; i < m; ++i) Arrays.fill(dist[i], Integer.MAX_VALUE);dist[0][0] = 0;boolean[][] seen = new boolean[m][n];while (!pq.isEmpty()) {int[] edge = pq.poll();int x = edge[0], y = edge[1], d = edge[2];if (seen[x][y]) continue;if (x == m - 1 && y == n - 1) break;seen[x][y] = true;for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if (nx >= 0 && nx < m && ny >= 0 && ny < n && Math.max(d, Math.abs(heights[nx][ny] - heights[x][y])) < dist[nx][ny]) {dist[nx][ny] = Math.max(d, Math.abs(heights[nx][ny] - heights[x][y]));pq.offer(new int[]{nx, ny, dist[nx][ny]});;}}}return dist[m - 1][n - 1];}
}

2454. 下一个更大元素 IV（双单调栈）

https://leetcode.cn/problems/next-greater-element-iv/?envType=daily-question&envId=2023-12-12

提示：

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

解法1——双单调栈

一个单调栈处理第一个更大的数，另一个处理第二个更大的数字。

如何确保了 stk2 的单调性呢？因为先处理了 stk2，可以确保在 stk1 的数据推入 stk2 之前，stk2 中 <= nums[i] 的数据都被弹出了，即 stk2 中存留的数据一定 大于 从 stk1 推入 stk2 的数据。

class Solution {public int[] secondGreaterElement(int[] nums) {int n = nums.length;int[] ans = new int[n];Arrays.fill(ans, -1);// 两个单调递减的单调栈Deque<Integer> stk1 = new ArrayDeque<>(), stk2 = new ArrayDeque<>();for (int i = 0; i < n; ++i) {// 判断是否是第二个更大的数字while (!stk2.isEmpty() && nums[i] > nums[stk2.peek()]) {ans[stk2.pop()] = nums[i];}// 使用ls存下弹出的结果List<Integer> ls = new ArrayList<>();while (!stk1.isEmpty() && nums[i] > nums[stk1.peek()]) {ls.add(stk1.pop());}for (int j = ls.size() - 1; j >= 0; j--) stk2.push(ls.get(j));stk1.push(i);}return ans;}
}

解法2——单调栈+优先队列

用一个单调队列代替其中一个单调栈，时间复杂度是 $O(nlogn)$

class Solution {public int[] secondGreaterElement(int[] nums) {int n = nums.length;int[] ans = new int[n];Arrays.fill(ans, -1);// 两个单调递减的单调栈Deque<Integer> stk = new ArrayDeque<>();PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> nums[x] - nums[y]);for (int i = 0; i < n; ++i) {// 判断是否是第二个更大的数字while (!pq.isEmpty() && nums[i] > nums[pq.peek()]) {ans[pq.poll()] = nums[i];}while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {pq.offer(stk.pop());}stk.push(i);}return ans;}
}

2697. 字典序最小回文串（贪心）

https://leetcode.cn/problems/lexicographically-smallest-palindrome/description/?envType=daily-question&envId=2023-12-13

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

回文串的相对应位置，两两判断取较小者即可。

class Solution {public String makeSmallestPalindrome(String s) {int n = s.length();char[] chs = s.toCharArray();for (int l = 0, r = n - 1; l < r; ++l, --r) {if (chs[l] < chs[r]) chs[r] = chs[l];else chs[l] = chs[r];}return new String(chs);}
}

2132. 用邮票贴满网格图⭐⭐⭐⭐⭐（二维前缀和+二维差分）

https://leetcode.cn/problems/stamping-the-grid/description/?envType=daily-question&envId=2023-12-14

提示：

m == grid.length
n == grid[r].length
1 <= m, n <= 10^5
1 <= m * n <= 2 * 10^5
grid[r][c] 要么是 0 ，要么是 1 。
1 <= stampHeight, stampWidth <= 10^5

用前缀和快速检查一片区域是否有占据位置；
用差分快速检查一个位置是否被覆盖。

class Solution {public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {int m = grid.length, n = grid[0].length;int[][] sum = new int[m + 1][n + 1], diff = new int[m + 2][n + 2];// 计算占据位置的前缀和 for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {sum[i + 1][j + 1] = grid[i][j] + sum[i + 1][j] + sum[i][j + 1] - sum[i][j];}}// 依次检查每个位置是否可以作为左上角，计算差分数组for (int i = 0; i + stampHeight - 1 < m; ++i) {for (int j = 0; j + stampWidth - 1 < n; ++j) {int x = i + stampHeight, y = j + stampWidth;int s = sum[x][y] - sum[i][y] - sum[x][j] + sum[i][j];if (s == 0) {diff[i + 1][j + 1]++;diff[i + 1][y + 1]--;diff[x + 1][j + 1]--;diff[x + 1][y + 1]++;}}}// 还原差分数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];if (diff[i][j] == 0 && grid[i - 1][j - 1] == 0) {return false;}}}return true;}
}

关于 前缀和 和 差分 可见：【算法基础】1.5 前缀和与差分

力扣上有二维前缀和的模板题目：304. 二维区域和检索 - 矩阵不可变

2415. 反转二叉树的奇数层

https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/description/?envType=daily-question&envId=2023-12-15

提示：

树中的节点数目在范围 [1, 2^14] 内
0 <= Node.val <= 10^5
root 是一棵 完美 二叉树

解法1——BFS 交换值

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode reverseOddLevels(TreeNode root) {Queue<TreeNode> q = new LinkedList<>();q.offer(root);boolean f = true;while (!q.isEmpty()) {int sz = q.size();List<TreeNode> ls = new ArrayList<>();for (int i = 0; i < sz; ++i) {TreeNode cur = q.poll();if (f && cur.left != null) {ls.add(cur.left);ls.add(cur.right);}if (cur.left != null) q.offer(cur.left);if (cur.right != null) q.offer(cur.right);}if (f) {for (int l = 0, r = ls.size() - 1; l < r; l++, r--) {int t = ls.get(l).val;ls.get(l).val = ls.get(r).val;ls.get(r).val = t;}}f = !f;}return root;}
}

解法2——镜像DFS 🐂

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode reverseOddLevels(TreeNode root) {dfs(root.left, root.right, 1);return root;}public void dfs(TreeNode a, TreeNode b, int d) {if (a == null) return;if (d % 2 == 1) swap(a, b);dfs(a.left, b.right, d + 1);dfs(a.right, b.left, d + 1);}public void swap(TreeNode a, TreeNode b) {int t = a.val;a.val = b.val;b.val = t;}
}

2276. 统计区间中的整数数目（平衡二叉搜索树/珂朵莉树）⭐⭐⭐⭐⭐

https://leetcode.cn/problems/count-integers-in-intervals/description/?envType=daily-question&envId=2023-12-16

提示：

1 <= left <= right <= 10^9
最多调用 add 和 count 方法 总计 10^5 次
调用 count 方法至少一次

珂朵莉树是一种以近乎暴力的形式存储区间信息的一个数据结构。方式是通过set存放若干个用结构体表示的区间，每个区间的元素都是相同的。

class CountIntervals {TreeMap<Integer, Integer> map = new TreeMap<>();int cnt = 0;public CountIntervals() {}public void add(int left, int right) {Map.Entry<Integer, Integer> interval = map.floorEntry(right);while (interval != null && interval.getValue() >= left) {int l = interval.getKey(), r = interval.getValue();left = Math.min(left, l);right = Math.max(right, r);cnt -= r - l + 1;map.remove(l);interval = map.floorEntry(right);}cnt += right - left + 1;map.put(left, right);}public int count() {return cnt;}
}/*** Your CountIntervals object will be instantiated and called as such:* CountIntervals obj = new CountIntervals();* obj.add(left,right);* int param_2 = obj.count();*/

746. 使用最小花费爬楼梯（线性DP）

https://leetcode.cn/problems/min-cost-climbing-stairs/description/?envType=daily-question&envId=2023-12-17

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;// dp[i]表示在第i层再走一步的最小花费int[] dp = new int[n];dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < n; ++i) {dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];}return Math.min(dp[n - 1], dp[n - 2]);}
}