happiness(栈)
// happiness
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000
// 函数声明
int max_happiness(int n, int w[]);
int main()
{
int n;
// 输入物品数量
scanf("%d", &n);
// 输入每个物品的满意度
int w[MAX_N];
for (int i = 0; i < n; i++)
{
scanf("%d", &w[i]);
}
// 输出最大happiness
printf("%d\n", max_happiness(n, w));
return 0;
}
int max_happiness(int n, int w[])
{
int prefix_sum[MAX_N + 1]; // 前缀和数组
int left[MAX_N]; // 每个物品的左边界
int right[MAX_N]; // 每个物品的右边界
int stack[MAX_N]; // 单调栈
int top; // 栈顶指针
int max_happiness = 0; // 记录最大happiness
// Step 1: 计算前缀和
prefix_sum[0] = 0;
for (int i = 1; i <= n; i++)
{
prefix_sum[i] = prefix_sum[i - 1] + w[i - 1];
}
// Step 2: 使用单调栈计算每个物品的左边界
top = -1; // 初始化栈为空
for (int i = 0; i < n; i++)
{
while (top != -1 && w[stack[top]] >= w[i])
{
top--;
}
if (top == -1)
{
left[i] = -1; // 没有比当前元素更小的,左边界为-1
}
else
{
left[i] = stack[top]; // 栈顶元素即为左边第一个比当前元素小的
}
stack[++top] = i; // 当前元素入栈
}
// Step 3: 使用单调栈计算每个物品的右边界
top = -1; // 清空栈
for (int i = n - 1; i >= 0; i--)
{
while (top != -1 && w[stack[top]] >= w[i])
{
top--;
}
if (top == -1)
{
right[i] = n; // 没有比当前元素更小的,右边界为n
}
else
{
right[i] = stack[top]; // 栈顶元素即为右边第一个比当前元素小的
}
stack[++top] = i; // 当前元素入栈
}
// Step 4: 计算最大happiness
for (int i = 0; i < n; i++)
{
int l = left[i] + 1; // 左边界+1
int r = right[i]; // 右边界
int total_sum = prefix_sum[r] - prefix_sum[l]; // 通过前缀和计算区间的总和
int current_happiness = total_sum * w[i]; // happiness计算公式
if (current_happiness > max_happiness)
{
max_happiness = current_happiness; // 更新最大happiness
}
}
return max_happiness;
}
标签:int,max,top,MAX,stack,happiness
From: https://www.cnblogs.com/yesno233233/p/18420751