代码随想录-Day55

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

方法一： 暴力解法

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            // 第一个柱子和最后一个柱子不接雨水
            if (i==0 || i== height.length - 1) continue;

            int rHeight = height[i]; // 记录右边柱子的最高高度
            int lHeight = height[i]; // 记录左边柱子的最高高度
            for (int r = i+1; r < height.length; r++) {
                if (height[r] > rHeight) rHeight = height[r];
            }
            for (int l = i-1; l >= 0; l--) {
                if(height[l] > lHeight) lHeight = height[l];
            }
            int h = Math.min(lHeight, rHeight) - height[i];
            if (h > 0) sum += h;
        }
        return sum;

    }
}

这段代码是用于解决「接雨水」问题的Java实现。给定一个数组 height，其中 height[i] 表示第 i 个位置的柱子的高度，目标是计算在这个直方图中能接多少雨水。这个问题的关键在于找到每个位置左右两边最高的柱子，以此来确定能够接住的雨水量。

代码解析

1. 初始化:

   • 创建一个变量 sum，用于累计接住的雨水总量。

2. 遍历并计算雨水量:

   • 遍历数组 height 中的每个元素，除了第一个和最后一个元素（因为它们无法形成封闭的空间来接雨水）。
   • 对于当前遍历到的元素 height[i]：
     • 计算右侧最高柱子的高度 rHeight 和左侧最高柱子的高度 lHeight。
     • 可以接住的雨水量取决于左右两边柱子中较低的那个与当前柱子高度的差值，即 Math.min(lHeight, rHeight) - height[i]。
     • 如果这个差值大于0，说明可以接住雨水，将其累加到 sum 中。

3. 返回结果:

   • 返回累计的雨水总量 sum。

时间复杂度和空间复杂度

• 时间复杂度: O(n^2)，其中 n 是数组 height 的长度。这是因为在遍历数组的过程中，对于每个元素，都需要再次遍历其左侧和右侧来寻找最高柱子，导致时间复杂度较高。
• 空间复杂度: O(1)，除了输入数组 height，代码中没有使用额外的数据结构，仅使用了几个变量进行计算。

总结

虽然这段代码能够正确解决接雨水问题，但是其时间复杂度较高，为 O(n^2)，在处理大数据量时效率低下。为了提高效率，可以采用动态规划或双指针技术，将时间复杂度降低到 O(n)。例如，可以预先计算每个位置左边最大高度和右边最大高度，或者使用双指针从两边向中间逼近，这样可以避免对每个元素进行二次遍历，显著提升算法性能。在实际应用中，优化算法的时间复杂度是提高程序运行效率的关键，特别是在处理大规模数据时尤为重要。

方法二：双指针

class Solution {
    public int trap(int[] height) {
        int length = height.length;
        if (length <= 2) return 0;
        int[] maxLeft = new int[length];
        int[] maxRight = new int[length];

        // 记录每个柱子左边柱子最大高度
        maxLeft[0] = height[0];
        for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);

        // 记录每个柱子右边柱子最大高度
        maxRight[length - 1] = height[length - 1];
        for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);

        // 求和
        int sum = 0;
        for (int i = 0; i < length; i++) {
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }
}

这段代码是用于解决「接雨水」问题的另一种Java实现，相较于之前的实现，它使用了动态规划的思想来优化算法的时间复杂度。目标依然是计算在一个直方图中能接多少雨水，但是这次通过预计算每个位置左右两边的最高柱子高度，避免了对每个位置的二次遍历，从而提高了算法效率。

代码解析

1. 初始化:

   • 创建两个数组 maxLeft 和 maxRight，分别用于存储每个位置左侧最大高度和右侧最大高度。
   • 创建变量 sum，用于累计接住的雨水总量。

2. 计算左侧最大高度:

   • 初始化 maxLeft[0] 为 height[0]，即数组的第一个元素。
   • 从左到右遍历数组，更新 maxLeft 数组中每个位置左侧的最大高度。

3. 计算右侧最大高度:

   • 初始化 maxRight[length - 1] 为 height[length - 1]，即数组的最后一个元素。
   • 从右到左遍历数组，更新 maxRight 数组中每个位置右侧的最大高度。

4. 计算雨水量:

   • 遍历数组，对于每个位置 i：
     • 计算可以接住的雨水量为左右两边柱子中较低的那个与当前柱子高度的差值，即 Math.min(maxLeft[i], maxRight[i]) - height[i]。
     • 如果这个差值大于0，说明可以接住雨水，将其累加到 sum 中。

5. 返回结果:

   • 返回累计的雨水总量 sum。

时间复杂度和空间复杂度

• 时间复杂度: O(n)，其中 n 是数组 height 的长度。这是因为算法分别进行了三次遍历：一次计算左侧最大高度，一次计算右侧最大高度，一次计算雨水量，每次遍历的时间复杂度均为 O(n)。
• 空间复杂度: O(n)，需要两个大小为 n 的数组 maxLeft 和 maxRight 来存储中间结果。

总结

这段代码通过预计算每个位置左右两边的最高柱子高度，避免了对每个位置进行二次遍历，从而将时间复杂度从 O(n^2) 优化到了 O(n)，显著提升了算法效率。这种方法在处理大数据量时尤其重要，能够确保算法在合理时间内完成计算。在实际应用中，动态规划是一种常用的优化算法时间复杂度的技术，通过将问题分解成更小的子问题并缓存子问题的结果，可以避免重复计算，提高算法效率。

方法三：双指针优化

class Solution {
    public int trap(int[] height) {
        if (height.length <= 2) {
            return 0;
        }
        // 从两边向中间寻找最值
        int maxLeft = height[0], maxRight = height[height.length - 1];
        int l = 1, r = height.length - 2;
        int res = 0;
        while (l <= r) {
            // 不确定上一轮是左边移动还是右边移动，所以两边都需更新最值
            maxLeft = Math.max(maxLeft, height[l]);
            maxRight = Math.max(maxRight, height[r]);
            // 最值较小的一边所能装的水量已定，所以移动较小的一边。
            if (maxLeft < maxRight) {
                res += maxLeft - height[l ++];
            } else {
                res += maxRight - height[r --];
            }
        }
        return res;
    }
}

这段代码是用于解决「接雨水」问题的又一种Java实现，它采用了双指针技术，从数组的两端向中间逼近，逐步计算能接住的雨水量。这种方法避免了预处理数组或多次遍历，使得算法的时间复杂度和空间复杂度均得到优化。

代码解析

1. 初始化:

   • 检查数组长度，如果长度小于等于2，直接返回0，因为至少需要三个柱子才能形成封闭空间来接雨水。
   • 初始化两个指针 l 和 r，分别指向数组的第二个元素和倒数第二个元素。
   • 初始化两个变量 maxLeft 和 maxRight，分别记录左侧和右侧当前遇到的最大高度。

2. 双指针逼近:

   • 使用循环，直到 l 和 r 相遇或交错。
   • 在每次循环中，更新 maxLeft 和 maxRight 的值，确保它们始终存储从开始位置到当前指针位置的最大高度。
   • 比较 maxLeft 和 maxRight 的值：
     • 如果 maxLeft 小于 maxRight，意味着左侧的高度不足以阻挡雨水，因此左侧的雨水量为 maxLeft - height[l]，将其累加到结果变量 res 中，并将左侧指针 l 向右移动一位。
     • 否则，右侧的高度不足以阻挡雨水，右侧的雨水量为 maxRight - height[r]，将其累加到结果变量 res 中，并将右侧指针 r 向左移动一位。

3. 返回结果:

   • 循环结束后，返回累计的雨水总量 res。

时间复杂度和空间复杂度

• 时间复杂度: O(n)，其中 n 是数组 height 的长度。这是因为双指针技术确保了每个元素仅被访问一次。
• 空间复杂度: O(1)，除了输入数组 height，代码中只使用了几个变量进行计算，没有额外的数据结构。

总结

这段代码通过双指针技术实现了对「接雨水」问题的有效求解，避免了预处理数组或多次遍历的高时间复杂度，同时在空间复杂度方面也得到了优化。双指针技术是一种常见的算法技巧，适用于多种问题，如寻找两个有序数组的中位数、求解两数之和等。在实际应用中，掌握双指针技术能够帮助我们更高效地解决许多类型的问题，特别是那些涉及到数组或列表的遍历和比较的问题。

方法四：单调栈

class Solution {
    public int trap(int[] height){
        int size = height.length;

        if (size <= 2) return 0;

        // in the stack, we push the index of array
        // using height[] to access the real height
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);

        int sum = 0;
        for (int index = 1; index < size; index++){
            int stackTop = stack.peek();
            if (height[index] < height[stackTop]){
                stack.push(index);
            }else if (height[index] == height[stackTop]){
                // 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的index
                stack.pop();
                stack.push(index);
            }else{
                //pop up all lower value
                int heightAtIdx = height[index];
                while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
                    int mid = stack.pop();

                    if (!stack.isEmpty()){
                        int left = stack.peek();

                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold = h * w;
                        if (hold > 0) sum += hold;
                        stackTop = stack.peek();
                    }
                }
                stack.push(index);
            }
        }

        return sum;
    }
}

这段代码是用于解决「接雨水」问题的另一种Java实现，它采用了单调栈的策略。单调栈是一种数据结构，可以用来快速找到数组中某个元素左侧或右侧的下一个更大或更小的元素，非常适合解决接雨水问题，因为要确定每个位置可以接住的雨水量，关键在于找到其左右两侧的最高柱子。

代码解析

1. 初始化:

   • 检查数组长度，如果长度小于等于2，直接返回0。
   • 创建一个单调栈 stack，用于存储数组元素的下标。
   • 初始化一个变量 sum，用于累计接住的雨水总量。

2. 遍历并维护单调栈:

   • 遍历数组 height 中的每个元素。
   • 对于当前遍历到的元素 height[index]：
     • 如果当前元素小于栈顶元素对应的值，将当前下标 index 入栈。
     • 如果当前元素等于栈顶元素对应的值，将栈顶元素弹出，因为相等的相邻墙，左边一个是不可能存放雨水的，然后将当前下标 index 入栈。
     • 如果当前元素大于栈顶元素对应的值，进入一个循环：
       • 弹出栈顶元素，直到栈为空或者栈顶元素对应的值不小于当前元素。
       • 对于每次弹出的元素，如果栈不为空，计算可以接住的雨水量，即左右两边柱子中较低的那个与弹出元素高度的差值乘以宽度（当前下标与栈顶下标的距离减1），将其累加到结果变量 sum 中。

3. 返回结果:

   • 返回累计的雨水总量 sum。

时间复杂度和空间复杂度

• 时间复杂度: O(n)，其中 n 是数组 height 的长度。每个元素至多被放入和弹出栈一次。
• 空间复杂度: O(n)，需要一个大小为 n 的单调栈 stack。

总结

这段代码通过使用单调栈，有效地解决了接雨水问题，避免了多次遍历数组，提高了算法效率。单调栈在处理这类问题时表现出色，能够快速找到特定条件下下一个更大或更小的元素，是解决与单调性相关的数组或序列问题的常用工具。在实际应用中，掌握单调栈的使用方法能够帮助解决一系列经典问题，提高代码效率和性能。

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

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

方法一：暴力解法

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int[] minLeftIndex = new int [length];
        int[] minRightIndex = new int [length];
        // 记录左边第一个小于该柱子的下标
        minLeftIndex[0] = -1 ;
        for (int i = 1; i < length; i++) {
            int t = i - 1;
            // 这里不是用if，而是不断向右寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        // 记录每个柱子右边第一个小于该柱子的下标
        minRightIndex[length - 1] = length;
        for (int i = length - 2; i >= 0; i--) {
            int t = i + 1;
            while(t < length && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < length; i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = Math.max(sum, result);
        }
        return result;
    }
}

这段代码是用于解决「最大矩形」问题的Java实现，其目标是在由非负整数构成的直方图中寻找最大矩形面积。给定一个数组 heights，其中 heights[i] 表示第 i 个位置的柱子的高度，问题是要找出直方图中最大的矩形面积。

代码解析

1. 初始化:

   • 创建两个数组 minLeftIndex 和 minRightIndex，分别用于存储每个柱子左侧第一个小于它的柱子的下标和右侧第一个小于它的柱子的下标。
   • 创建变量 result，用于存储最大的矩形面积。

2. 计算左侧最小下标:

   • 初始化 minLeftIndex[0] 为 -1，即数组的最左侧。
   • 从左到右遍历数组，对于每个位置 i，使用一个变量 t 来追踪左侧第一个小于 heights[i] 的柱子的下标。如果当前位置的柱子高度小于等于左侧柱子的高度，就继续向左寻找，直到找到一个小于它的柱子为止，或者到达数组边界。

3. 计算右侧最小下标:

   • 初始化 minRightIndex[length - 1] 为 length，即数组的最右侧。
   • 从右到左遍历数组，对于每个位置 i，使用一个变量 t 来追踪右侧第一个小于 heights[i] 的柱子的下标。如果当前位置的柱子高度小于等于右侧柱子的高度，就继续向右寻找，直到找到一个小于它的柱子为止，或者到达数组边界。

4. 计算最大矩形面积:

   • 遍历数组，对于每个位置 i，计算以该柱子为底边的矩形面积，即 heights[i] 乘以宽度，宽度为 minRightIndex[i] - minLeftIndex[i] - 1。
   • 更新 result，使其始终保持最大面积的值。

5. 返回结果:

   • 返回最终计算出的最大矩形面积 result。

时间复杂度和空间复杂度

• 时间复杂度: O(n)，其中 n 是数组 heights 的长度。算法分别进行了三次遍历：一次计算左侧最小下标，一次计算右侧最小下标，一次计算最大矩形面积，每次遍历的时间复杂度均为 O(n)。
• 空间复杂度: O(n)，需要两个大小为 n 的数组 minLeftIndex 和 minRightIndex 来存储中间结果。

总结

这段代码通过预计算每个柱子左右两侧第一个小于它的柱子的下标，避免了对每个位置进行多次遍历来寻找最优解，从而将时间复杂度从 O(n^2) 优化到了 O(n)，显著提升了算法效率。这种方法在处理大数据量时尤其重要，能够确保算法在合理时间内完成计算。在实际应用中，这种通过预处理数据来加速计算的策略是解决复杂问题的常见手段，通过将问题分解成更小的子问题并提前计算关键信息，可以避免重复计算，提高算法效率。

方法二：单调栈

class Solution {
    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();
        
        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;
        
        st.push(0);
        int result = 0;
        // 第一个元素已经入栈，从下标1开始
        for (int i = 1; i < heights.length; i++) {
            // 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
                st.pop(); // 这个可以加，可以不加，效果一样，思路不同
                st.push(i);
            } else {
                while (heights[i] < heights[st.peek()]) { // 注意是while
                    int mid = st.peek();
                    st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                st.push(i);
            }
        }
        return result;
    }
}

这段代码是用于解决「最大矩形」问题的另一种Java实现，它采用了单调栈的策略。问题的核心是在由非负整数构成的直方图中寻找最大矩形面积。给定一个数组 heights，其中 heights[i] 表示第 i 个位置的柱子的高度，目标是找到直方图中最大的矩形面积。

代码解析

1. 初始化与数组扩容:

   • 创建一个单调栈 st，用于存储数组元素的下标。
   • 为了便于处理边界条件，首先对数组 heights 进行扩容，即在头部和尾部各添加一个高度为0的虚拟柱子，这样可以简化后续的逻辑处理。

2. 遍历并维护单调栈:

   • 初始化栈，将第一个元素的下标 0 入栈。
   • 从下标 1 开始遍历数组 heights。
   • 对于当前遍历到的元素 heights[i]：
     • 如果当前元素高度大于栈顶元素对应的值，将当前下标 i 入栈。
     • 如果当前元素高度等于栈顶元素对应的值，可以将栈顶元素弹出，再将当前下标 i 入栈（注：这里弹出栈顶元素并非必要步骤，但不影响最终结果，仅影响栈内元素的分布）。
     • 如果当前元素高度小于栈顶元素对应的值，进入一个循环：
       • 不断弹出栈顶元素，直到栈为空或者栈顶元素对应的值不大于当前元素高度。
       • 对于每次弹出的元素，计算可以形成的矩形面积，即高度乘以宽度（当前下标 i 减去栈顶下标再减1），更新最大面积 result 的值。
       • 循环结束后，将当前下标 i 入栈。

3. 返回结果:

   • 返回计算出的最大矩形面积 result。

时间复杂度和空间复杂度

• 时间复杂度: O(n)，其中 n 是数组 heights 的长度。每个元素至多被放入和弹出栈一次。
• 空间复杂度: O(n)，需要一个大小为 n 的单调栈 st。

总结

这段代码通过使用单调栈，有效地解决了最大矩形问题，避免了多次遍历数组来寻找最优解，提高了算法效率。单调栈在处理这类问题时表现出色，能够快速找到特定条件下下一个更大或更小的元素，是解决与单调性相关的数组或序列问题的常用工具。在实际应用中，掌握单调栈的使用方法能够帮助解决一系列经典问题，提高代码效率和性能。通过适当的数据结构和算法设计，如这里的单调栈，可以显著减少时间复杂度，使算法在处理大规模数据时也能保持高效。

方法三：单调栈精简

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] newHeight = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeight, 1, heights.length);
        newHeight[heights.length+1] = 0;
        newHeight[0] = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        int res = 0;
        for (int i = 1; i < newHeight.length; i++) {
            while (newHeight[i] < newHeight[stack.peek()]) {
                int mid = stack.pop();
                int w = i - stack.peek() - 1;
                int h = newHeight[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);

        }
        return res;
    }
}

这段代码是用于解决「最大矩形」问题的Java实现，其目标是在由非负整数构成的直方图中找到具有最大面积的矩形。给定一个数组 heights，其中 heights[i] 表示直方图中第 i 个柱子的高度，算法的任务是确定这个直方图中可以形成的具有最大面积的矩形。

代码解析

1. 初始化与数组扩容:

   • 创建一个新数组 newHeight，长度为原数组 heights 长度加上2，这样做是为了简化边界条件的处理。
   • 将原数组 heights 的内容复制到 newHeight 的中间部分，同时在 newHeight 的头部和尾部各添加一个高度为0的元素。这样可以确保算法在处理边界柱子时不会出现下标越界的情况。

2. 创建单调栈:

   • 创建一个单调栈 stack，用于存储柱子的下标，初始时将 newHeight 的第一个元素下标 0 入栈。

3. 遍历并维护单调栈:

   • 从下标 1 开始遍历 newHeight。
   • 对于当前遍历到的元素 newHeight[i]：
     • 如果当前元素的高度小于栈顶元素对应的高度，即 newHeight[i] < newHeight[stack.peek()]，则：
       • 进入一个循环，持续弹出栈顶元素直到栈为空或当前元素高度大于等于栈顶元素高度。
       • 对于每次弹出的元素，计算可以形成的矩形面积，即高度乘以宽度（当前下标 i 减去栈顶下标再减1），并更新最大面积 res 的值。
     • 无论当前元素高度与栈顶元素高度的比较结果如何，都将当前下标 i 入栈。

4. 返回结果:

   • 算法完成后，返回计算出的最大矩形面积 res。

时间复杂度和空间复杂度

• 时间复杂度: O(n)，其中 n 是数组 heights 的长度。每个元素至多被放入和弹出栈一次。
• 空间复杂度: O(n)，需要一个大小为 n 的单调栈 stack 和一个长度为 heights.length + 2 的数组 newHeight。

总结

这段代码通过使用单调栈策略，有效地解决了最大矩形问题，避免了多次遍历数组来寻找最优解，提高了算法效率。单调栈在这里用于快速找到每个柱子左侧和右侧第一个低于它的柱子，进而计算出以该柱子为高度的最大矩形面积。在实际应用中，单调栈是一种非常实用的数据结构，尤其适合处理与单调性有关的问题，如寻找下一个更大或更小的元素、计算直方图最大矩形面积等。通过巧妙地利用单调栈，可以显著降低算法的时间复杂度，使程序在处理大规模数据时仍能保持高效。