练习题
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;};
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; }
|
补充练习题
参考资料