ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客网]小A的柱状图(单调栈)

2022年6月8日 200点热度 2人点赞 0条评论

题目链接:小A的柱状图 (nowcoder.com)

之前写个一道差不多的题:Largest Rectangle in a Histogram(单调栈)

题目大意 / Problem

柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形,但是小A的柱状图却不是一个规范的柱状图,它的每个矩形下端的宽度可以是不相同的一些整数,分别为a[i]a[i]a[i],每个矩形的高度是h[i]h[i]h[i],现在小A只想知道,在这个图形里面包含的最大矩形面积是多少。

图片来自牛客网

思路 / Thought

用单调栈来维护一个点往左和向右分别可以延长多少。

构造一个单调不减栈,以从左往右为例。也就是当h[i]大于栈内最大高度时直接加入到栈中,说明左边不存在比h[i]更高的柱形,也就是说向左延伸距离为0。

只要栈顶存在且高度大于等于h[i]说明从i这个点可以向左延伸,就将栈顶单位的宽度加入到l[i]中。

最后将l[i] + 1存入栈中,因为l[i] + 1个单位都被合并到i这个单位中了,以便于加到后面的单位中。

计算r[i]只需要改变方向即可,不要忘记清空栈。

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
//64bit IO Format: %lld 
using namespace std;
const int maxn = 1e6 + 9;
int a[maxn], b[maxn], prefix[maxn];
int l[maxn], r[maxn];//分别表示左右最大宽度 
pair<int, int> stk[maxn];//{宽度,高度}
int top = 0;//构造单调递增栈 

signed main()
{
	int N;scanf("%lld", &N);
	for(int i = 1;i <= N; ++ i)scanf("%lld", a + i);
	for(int i = 1;i <= N; ++ i)scanf("%lld", b + i);
	for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] + a[i];
	for(int i = 1;i <= N; ++ i)
	{
		while(top && b[i] <= stk[top].se)l[i] += stk[top --].fi;
		stk[++ top] = {l[i] + 1, b[i]};
	}
	top = 0;
	for(int i = N;i >= 1; -- i)
	{
		while(top && b[i] <= stk[top].se)r[i] += stk[top --].fi;
		stk[++ top] = {r[i] + 1, b[i]};
	}
	int ans = 0;
	for(int i = 1;i <= N; ++ i)
	{
		int tmp = (prefix[i + r[i]] - prefix[i - l[i] - 1]) * b[i];
		ans = max(ans, tmp);
	}
	printf("%lld\n" ,ans);
	return 0;
}
 
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 单调栈 思维 牛客网 算法 算法竞赛
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意 / Problem
  • 思路 / Thought
  • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号