算法刷题记录——LeetCode篇(1.9) [第81~90题](持续更新)

更新时间：2025-04-10

• 算法题解目录汇总：算法刷题记录——题解目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1：

输入：heights = [2,1,5,6,2,3]
输出：10

解释：最大的矩形为图中红色区域，面积为 10。

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

方法：单调栈法

利用单调栈分别计算每个柱子的左右边界，从而高效求解最大矩形面积。

1. 左右边界确定：

   • 使用单调递增栈分别计算每个柱子的左右第一个较小柱子的位置
   • 左边界数组left存储每个柱子左侧最近的小于当前高度的索引
   • 右边界数组right存储每个柱子右侧最近的小于当前高度的索引

2. 单调栈操作：

   • 左边界计算：从左向右遍历，维护单调递增栈，遇到较小值时弹出栈顶元素
   • 右边界计算：从右向左遍历，同样维护单调递增栈，处理逻辑与左边界对称

3. 面积计算：

   • 对于每个柱子，有效宽度为right[i] - left[i] - 1
   • 当前柱子贡献的面积为高度 × 宽度
   • 遍历所有柱子维护最大面积

代码实现(Java)：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];  // 存储每个柱子左边第一个小于当前高度的索引
        int[] right = new int[n]; // 存储每个柱子右边第一个小于当前高度的索引
        Deque<Integer> stack = new ArrayDeque<>();

        // 计算左边界
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // 计算右边界
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        // 计算最大面积
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = right[i] - left[i] - 1;
            maxArea = Math.max(maxArea, heights[i] * width);
        }
        return maxArea;
    }
}

复杂度分析：

• 时间复杂度：O(n)，三次遍历时间复杂度均为 O(n)，每个元素最多入栈和出栈各一次。
• 空间复杂度：O(n)（存储左右边界数组和栈空间）。

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]

解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。

注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

进阶：
你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

方法：逆向双指针

从两个数组的末尾（最大值）开始比较，依次将较大的元素放入 nums1 的末尾空位，避免覆盖未处理的元素。具体步骤如下：

1. 指针初始化：

   • i 指向 nums1 有效元素的末尾（m-1）
   • j 指向 nums2 的末尾（n-1）
   • k 指向合并后的数组末尾（m+n-1）

2. 逆向遍历合并：

   • 比较 nums1[i] 和 nums2[j]，将较大的值放入 nums1[k]，并移动对应指针。
   • 重复直到其中一个数组处理完。

3. 处理剩余元素：

   • 若 nums2 还有剩余元素，直接复制到 nums1 前端。

代码实现(Java)：

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;      // nums1有效元素的末尾指针
        int j = n - 1;      // nums2的末尾指针
        int k = m + n - 1;  // 合并后的末尾指针
      
        // 逆向遍历比较并合并
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
      
        // 处理nums2剩余元素（若存在）
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

复杂度分析：

• 时间复杂度：O(m+n)，
• 空间复杂度：O(1)（无需额外空间）。

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。