84. 柱状图中最大的矩形

84. 柱状图中最大的矩形
在这里插入图片描述

C代码：暴力：遍历所有可能

int largestRectangleArea(int* heights, int heightsSize){// 直接遍历所有可能：超出时间限制int ans = 0;for (int l = 0; l < heightsSize; ++l) {int minHeight = INT_MAX;for (int r = l; r < heightsSize; ++r) {minHeight = fmin(minHeight, heights[r]);ans = fmax(ans, (r - l + 1) * minHeight);}}return ans;
}

C代码：单调栈

int largestRectangleArea(int* heights, int heightsSize)
{int stack[heightsSize];int top = -1;stack[++top] = 0;int max = -1;int temp = 0;for(int i = 1; i < heightsSize; i++) {if(heights[i] >= heights[stack[top]]) {  // 递增栈stack[++top] = i;} else {while(top != -1 && heights[i] < heights[stack[top]]) { // 递增栈：栈顶大于当前元素的，全部出栈if (top == 0) {temp = i * heights[stack[top]];} else {temp = (i - stack[top-1] - 1) * heights[stack[top]]; // 6*1、5*2、1*3...}max = fmax(max, temp);--top;}stack[++top] = i;}}while(top != -1) { // 遍历完数组，单调栈还有一批递增元素if (top == 0) {temp = (heightsSize) * heights[stack[top]];} else {temp = (heightsSize - 1 - stack[top-1]) * heights[stack[top]];}max = fmax(max, temp);--top;}return max;
}