代码随想录算法训练营第四十八天|Day48 单调栈

42. 接雨水

https://programmercarl.com/0042.%E6%8E%A5%E9%9B%A8%E6%B0%B4.html

思路

int trap(int* height, int heightSize) {
    int ans = 0;
    int left = 0, right = heightSize - 1;              
    int leftMax = 0, rightMax = 0;                     
    while (left < right) {                             
        leftMax = fmax(leftMax, height[left]);
        rightMax = fmax(rightMax, height[right]);
        if (leftMax < rightMax) {
            ans += leftMax - height[left];              
            ++left;
        }
        else {
            ans += rightMax - height[right];           
            --right;
        }
    }
    return ans;
}

学习反思

用来计算雨水收集的总量的。它使用了双指针的方法来遍历数组，并计算左侧和右侧的最大高度。在遍历的过程中，根据左右两侧的最大高度来确定当前位置可以收集的雨水量。代码的思路比较清晰，先定义了结果变量 ans，并初始化左右指针 left 和 right。同时，定义了左右两侧的最大高度变量 leftMax 和 rightMax。然后使用 while 循环，当左指针小于右指针时，进行遍历。在遍历的过程中，使用 fmax 函数更新左右两侧的最大高度。然后，根据左右两侧的最大高度来判断当前位置可以收集的雨水量。如果左侧最大高度小于右侧最大高度，则更新 ans，并将左指针右移。否则，更新 ans，并将右指针左移。最后，返回 ans 作为结果。整体来说，这段代码使用了双指针的方法，时间复杂度为 O(n)，空间复杂度为 O(1)。

柱状图中最大的矩形

https://programmercarl.com/0084.%E6%9F%B1%E7%8A%B6%E5%9B%BE%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2.html

思路

int largestRectangleArea(int* heights, int heightsSize) {
    int* stack = (int*)malloc(heightsSize * sizeof(int));
    int top = -1; 
    int maxArea = 0; 
    int i;
    for (i = 0; i < heightsSize; i++) {
        while (top != -1 && heights[i] < heights[stack[top]]) {
            int h = heights[stack[top--]]; 
            int width = (top == -1) ? i : (i - stack[top] - 1); 
            maxArea = maxArea > h * width ? maxArea : h * width; 
        }
        stack[++top] = i; 
    }
    while (top != -1) {
        int h = heights[stack[top--]]; 
        int width = (top == -1) ? i : (i - stack[top] - 1); 
        maxArea = maxArea > h * width ? maxArea : h * width;
    }
    free(stack);
    return maxArea; 
}

学习反思

使用栈来记录直方图的索引。遍历直方图数组，如果当前直方图高度小于栈顶直方图高度，则栈顶直方图所形成的矩形面积可以计算出来了。计算方法是以栈顶直方图为高，栈顶索引与当前索引之间的宽度为宽。计算完后，将栈顶元素出栈继续计算，直到栈为空或者当前直方图高度大于栈顶直方图高度。将当前索引入栈。遍历结束后，栈中可能还存在一些直方图，这是因为这些直方图的右边界还未遍历到，所以可以将这些直方图按照右边界为数组长度的方式计算矩形面积。最后返回计算得到的最大矩形面积。该算法的时间复杂度是O(n)，空间复杂度是O(n)。

总结

加油！！！