日度归档：28 10 月, 2018

Openjudge BJUTACM 2018 周末集训 1005:Largest Rectangle in a Histogram

发表评论

可以说是非常不好想也非常不好做的一道题了……大佬的提示是单调栈，自己随便想了想就开始写，结果就挂掉了，然后看题解，也没太大用，最后是单步调试让我差不多搞清楚了。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
}