抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

七つの海

ひと結び、人を結んで

练习题

LeetCode - 柱状图中的最大矩形

题目地址:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> s;
const int n = heights.size();
int *L = new int[n+1]{0};
int *R = new int[n+1]{0};
for(int i = 0;i < n;++i) {
while(s.size() && heights[s.top()] > heights[i]) {
R[s.top()] = i;
s.pop();
}
if(s.empty()) L[i] = -1;
else L[i] = s.top();
s.push(i);
}
while(!s.empty()) {
R[s.top()] = n;
s.pop();
}
int ans = 0, tmp;
for(int i = 0;i < n;++i) {
tmp = heights[i]*(R[i]-L[i]-1);
if(tmp > ans) ans = tmp;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <stack>
#include <algorithm>

#define npos (n+1)

using namespace std;
typedef long long longs;

const int N = 1e5+5;
int h[N],l[N],r[N];
longs ans;

inline void pop(stack<int> &s, int i)
{
r[s.top()] = i;
s.pop();
}

inline void push(stack<int> &s, int i, int a[])
{
while(s.size()&&a[s.top()]>a[i])pop(s,i);
if(s.empty()) l[i] = 0;
else l[i] = s.top();
s.push(i);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
while(cin>>n&&n)
{
stack<int> s;
ans = 0;
for(int i=1;i<=n;++i)
{
cin>>h[i];
push(s,i,h);
}
while(!s.empty())
pop(s,npos);
for(int i=1;i<=n;++i)
ans = max(ans,(longs)h[i]*(r[i]-l[i]-1));
cout<<ans<<endl;
}

return 0;
}

洛谷 P4147

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;
typedef long long longs;

struct item{int w,h;}; // w是宽度,h是高度

const int N = 1050;
int n,m;
char in;
int tmph[N]{0}; // 可维持的最好高度
int ans = 0;

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

stack<item> s; // 严格递减的单调栈

cin>>n>>m;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
cin>>in;
if(in=='F') ++tmph[j];
else tmph[j] = 0;
int tmpw = 0; // 可维持的最好宽度
while(!s.empty()&&s.top().h>=tmph[j]) // 可以延长
{
tmpw += s.top().w; // 外延宽度
ans = max(ans,s.top().h*tmpw);
s.pop();
}
s.push({tmpw+1,tmph[j]}); // 增加自己的宽度
}

int tmpw = 0;
while(!s.empty()) // 出来时最好高度是严格递减的,均可外延
{
tmpw += s.top().w;
ans = max(ans,s.top().h*tmpw); // 反向外延更新答案
s.pop();
}
}
longs out = 3ll*ans;
cout<<out<<endl;

return 0;
}

补充练习题

参考资料

评论