力扣实训 _ [240]. 搜索二维矩阵 II _ [739].每日温度

搜索二维矩阵 II

1. 题目回顾

题目描述：
编写一个高效的算法来搜索m x n矩阵matrix中的一个目标值target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

核心概念：

• 双重单调性：矩阵在水平和垂直方向上都是有序的。
• 二分法的适用性：既然每一行和每一列都是有序的，我们自然可以联想到利用二分法来加速查找，而不是逐行逐列地线性扫描。

示例：

• 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
• 输出：true

2. 核心思路：二分法在二维矩阵中的应用

针对这道题，二分法有两种截然不同的应用形式，分别对应不同的时间复杂度：

• 形式一：逐行二分查找（基础二分）
  既然每一行都是有序的，我们可以遍历每一行，在当前行内使用基础二分查找寻找target。这种方法逻辑简单，是对一维二分法的直接扩展。
• 形式二：对角线二分 + 递归分治（高级二分）
  利用矩阵的全局双重单调性，我们可以选取矩阵的主对角线。对角线上的元素也是严格递增的，因此可以对对角线进行二分查找，快速定位target可能存在的“候选区域”，从而将二维搜索空间切割为更小的子矩阵进行递归搜索。

3. 算法详细步骤

3.1 逐行二分查找步骤

1. 遍历矩阵：依次取出矩阵的每一行。
2. 一维二分：在当前行内，设定左右指针left = 0,right = n - 1。
3. 区间收缩：计算中点mid，若matrix[row][mid] == target则返回true；若小于target，则left = mid + 1；若大于target，则right = mid - 1。
4. 进入下一行：若当前行未找到，继续遍历下一行。

3.2 对角线二分 + 递归分治步骤

1. 对角线二分：在矩阵的主对角线上进行二分查找，寻找第一个大于target的对角线元素（即寻找 Upper Bound）。
2. 确定候选区域：假设找到的对角线索引为row，那么target只可能存在于两个子矩阵中：
   • 右上区域：行范围[0, row-1]，列范围[row, n-1]。
   • 左下区域：行范围[row, m-1]，列范围[0, row-1]。
3. 递归搜索：对这两个子矩阵递归执行上述二分与分割过程，直到找到目标或搜索空间为空。

4. 代码实现

class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) return false; // 1. 遍历矩阵的每一行 for (int[] row : matrix) { // 2. 对当前行执行标准的基础二分查找 int left = 0, right = row.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (row[mid] == target) { return true; // 找到目标，直接返回 } else if (row[mid] < target) { left = mid + 1; // 目标在右半部分 } else { right = mid - 1; // 目标在左半部分 } } } return false; // 所有行均未找到 } }

5. 复杂度分析

逐行二分查找

• 时间复杂度： O(mlog⁡n)
  需要对 m 行分别进行二分查找，每次二分查找的时间复杂度为 O(log⁡n) 。
• 空间复杂度： O(1)
  仅使用了常数级别的额外变量。

---

每日温度

1. 题目回顾

题目描述：
给定一个整数数组temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是指对于第i天，下一个比当前温度更高的温度需要等待的天数。如果之后都不会出现更高的温度，则answer[i] = 0。

核心概念：

• 下一个更大元素（Next Greater Element）：这是算法中非常经典的一类问题。我们需要为数组中的每一个元素，找到其右侧第一个比它大的元素。
• 单调栈（Monotonic Stack）：为了高效地解决“下一个更大元素”问题，我们需要维护一个栈，使得栈中的元素始终保持单调递增或单调递减的顺序。

示例：

• 输入：temperatures = [73,74,75,71,69,72,76,73]
• 输出：[1,1,4,2,1,1,0,0]
• 解释：
  • 第 0 天温度 73，第 1 天 74 更高，等待 1 天。
  • 第 2 天温度 75，直到第 6 天 76 才更高，等待 4 天。
  • 第 6 天和第 7 天之后没有更高的温度，等待 0 天。

2. 核心思路：单调递减栈

这道题是单调栈的绝对经典应用。

• 常规思维（暴力双重循环）：对于每一天，向后遍历寻找第一个比它高的温度。时间复杂度为 O(n2)O(n2) ，在数据量大时会超时。
• 进阶思维（单调栈）：我们可以维护一个单调递减栈，栈中存储的是数组的索引。
  • 遍历数组时，如果当前温度大于栈顶索引对应的温度，说明我们找到了栈顶元素的“下一个更高温度”。
  • 此时，我们将栈顶元素弹出，并计算等待天数（当前索引 - 栈顶索引）。
  • 不断重复上述弹出和计算的过程，直到栈为空或当前温度不再大于栈顶温度。
  • 最后，将当前索引入栈。
• 核心洞察：栈中保留的都是“还在等待更高温度”的天数。一旦遇到高温，就能批量解决那些等待者的问题。

3. 算法详细步骤

3.1 初始化

• 创建一个结果数组answer，长度与temperatures相同，初始值全为 0（处理找不到更高温度的情况）。
• 创建一个栈stack，用于存储温度的索引。

3.2 遍历温度数组

对于每一天i（从 0 到 n-1）：

1. 循环检查栈顶：当栈不为空，且当前温度temperatures[i]大于栈顶索引对应的温度temperatures[stack.peek()]时：
   • 弹出栈顶索引prevIndex = stack.pop()。
   • 计算等待天数：answer[prevIndex] = i - prevIndex。
2. 当前索引入栈：将当前索引i压入栈中。此时栈依然保持单调递减的特性。

3.3 返回结果

遍历结束后，栈中可能还会剩下一些索引，这些索引对应的天数之后都没有更高的温度。由于answer数组初始化为 0，所以无需额外处理，直接返回answer即可。

4. 代码实现

class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; // 1. 初始化结果数组，默认值为 0（处理之后没有更高温度的情况） int[] answer = new int[n]; // 2. 初始化单调递减栈，存储的是温度的【索引】 Deque<Integer> stack = new ArrayDeque<>(); // 3. 遍历每一天的温度 for (int i = 0; i < n; i++) { // 当栈不为空，且当前温度大于栈顶索引对应的温度时 // 说明找到了栈顶元素的“下一个更高温度” while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { // 弹出栈顶元素（即等待更高温度的那一天） int prevIndex = stack.pop(); // 计算等待的天数 = 当前索引 - 之前的索引 answer[prevIndex] = i - prevIndex; } // 将当前索引入栈，等待未来更高温度的到来 stack.push(i); } return answer; } }

5. 复杂度分析

假设数组的长度为 n 。

• 时间复杂度： O(n)
  虽然代码中有一个while循环嵌套在for循环内部，看起来像是 O(n2) ，但实际上每个元素最多只会入栈一次、出栈一次。因此，整个过程中栈操作的总次数是 2n ，摊薄到每个元素上是 O(1) ，总时间复杂度为线性级别 O(n) 。
• 空间复杂度： O(n)
  需要一个额外的栈来存储索引。在最坏的情况下（例如温度数组是严格递减的，如[5,4,3,2,1]），所有的索引都会被压入栈中，栈的空间占用为 O(n)。