可以说是非常不好想也非常不好做的一道题了……大佬的提示是单调栈，自己随便想了想就开始写，结果就挂掉了，然后看题解，也没太大用，最后是单步调试让我差不多搞清楚了。Solve()函数里的每一行都博大精深，有很多用。我也实在讲不清楚，把AC代码发上来，再贴几个题解连接参考一下吧。
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 | #include<cstdio> #include<stack> #include<vector> #include<algorithm> using namespace std; long long solve(vector<long long> & heights) { long long remax = 0; stack<long long> spos; heights.push_back(0); for (int i = 0; i < heights.size(); i++) { while (!spos.empty() && heights[spos.top()] >= heights[i]) { int curpos = spos.top(); spos.pop(); remax = max(remax, heights[curpos] * (spos.empty() ? i : ((i - 1) - (spos.top() + 1) + 1))); //这里大部分题解写的是i-spos.top()-1，我搞明白之后把这里写成了易于理解的形式 } spos.push(i); } return remax; } int main() { do { int n; scanf("%d", &n); if (n == 0)break; vector<long long> v; for (int i = 1; i <= n; i++) { long long x; scanf("%lld", &x); v.push_back(x); } printf("%lld", solve(v)); } while (1); } |
此题为LeetCode原题：https://leetcode.com/problems/largest-rectangle-in-histogram/description/
该题BJUTACM地址：http://bjutacm.openjudge.cn/bjut2018/1005/
（数据范围有可能会不相同）
题解：
https://www.cnblogs.com/grandyang/p/4322653.html
https://blog.csdn.net/princexiexiaofeng/article/details/79652003
https://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html
https://tech.pic-collage.com/algorithm-largest-area-in-histogram-84cc70500f0c
我个人看题解是没看懂的，单步调试拯救了我。。如果看不懂就单步吧。。有的地方我没解释清楚，从网上搜搜题解就好。
强烈建议这道题单步跟，多跟几个样例，不单步你看不懂其中的逻辑。。
我按照雪花大佬做法写的，经我垃圾的改编加了一堆cruft：不要问我怎么回事我也搞不清楚
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 | #include<cstdio> #include<stack> #include<vector> #include<algorithm> using namespace std; struct P { long long h, i; }; long long solve(vector<long long> & heights) { long long remax = 0; stack<P> s; heights.push_back(0); for (int i = 0; i < heights.size(); i++) { long long l = i; while (!s.empty() && s.top().h > heights[i]){ l = s.top().i; remax = max(remax, s.top().h * ( (i - 1) - s.top().i + 1)); s.pop(); } s.push(P{ heights[i],l }); } return remax; } int main() { do { int n; scanf("%d", &n); if (n == 0)break; vector<long long> v; for (int i = 1; i <= n; i++) { long long x; scanf("%lld", &x); v.push_back(x); } printf("%lld\n", solve(v)); } while (1); } |
雪花大佬的不cruft的代码
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 | #include <iostream> #include <algorithm> using namespace std; using ll = long long; struct Candidate { // candidate rectangle. area = height * (end_pos - start_pos) ll h; // the height ll i; // the start position; // end position is implied }; Candidate monostack[100100]; ll size = 0; ll max_area = 0; void monostack_push(ll h, ll i) { ll pos = i; // start pos while (size > 0 && monostack[size - 1].h >= h) { // equality is optional Candidate const & p = monostack[--size]; // pop pos = p.i; // update start pos max_area = max(max_area, p.h * (i - p.i)); } monostack[size++] = {h, pos}; // push } int main() { // init size = 0; max_area = 0; // for each input // monostack_push(height, pos); // monostack_push(0, last pos + 1); // another trick // output max_area } |