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)。
柱状图中最大的矩形
思路
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)。
总结
加油！！！
标签：int,top,ans,随想录,直方图,Day48,第四十八,stack,maxArea From： https://blog.csdn.net/a6666999d/article/details/143823479