0084-largest-rectangle-in-histogram.c

const int MAX_N = 1e5 + 5;
struct Stack
{
	int top;
	int capacity;
	int *array;
};

struct Stack *createStack()
{
	struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
	stack->capacity = MAX_N;
	stack->top = -1;
	stack->array = (int *)malloc(stack->capacity * sizeof(int));
	return stack;
}

int isFull(struct Stack *stack)
{
	return stack->top == stack->capacity - 1;
}

int isEmpty(struct Stack *stack)
{
	return stack->top == -1;
}

void push(struct Stack *stack, int val)
{
	if (isFull(stack))
		return;
	stack->array[++stack->top] = val;
}

void pop(struct Stack *stack)
{
	if (isEmpty(stack))
		return;
	--stack->top;
}

int peek(struct Stack *stack)
{
	if (isEmpty(stack))
		return INT_MIN;
	return stack->array[stack->top];
}

int max(int num1, int num2)
{
	return (num1 > num2) ? num1 : num2;
}

int largestRectangleArea(int *heights, int heightsSize)
{
	int ans = 0;
	struct Stack *st = createStack();
	for (int i = 0; i < heightsSize; i++)
	{
		while (!isEmpty(st) && heights[peek(st)] > heights[i])
		{
			int tp = peek(st);
			pop(st);
			int dist = (isEmpty(st) ? i : i - peek(st) - 1);
			ans = max(ans, dist * heights[tp]);
		}
		push(st, i);
	}
	while (!isEmpty(st))
	{
		int tp = peek(st);
		pop(st);
		int dist = (isEmpty(st) ? heightsSize : heightsSize - peek(st) - 1);
		ans = max(ans, dist * heights[tp]);
	}
	return ans;
}