【每日一题 春季7】131. 直方图中最大的矩形 & 456. 132模式

发表于 更新于 分类于 Valine：
本文字数： 194 阅读时长 ≈ 1 分钟

Day7 AcWing 131. 直方图中最大的矩形
Day7 LeetCode 456. 132模式

思路

  1. 单调栈

直方图中最大的矩形

132模式 单调栈

$a_i < a_j > a_k$
从右往左扫描，右侧维护一个单调栈，当栈非空的时候，只要 $a_j$ 大于左边的元素 $a_i$ ，则满足132模式

拓展

  1. LeetCode 84. 柱状图中最大的矩形
  2. 单调栈

代码

131. 直方图中最大的矩形
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
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int h[N], l[N], r[N];
int q[N];

int main()
{
    while (scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
        h[0] = h[n + 1] = -1;

        // 求左边界
        int tt = 0;
        q[0] = 0;
        for (int i = 1; i <= n; i ++ )
        {
            while (h[q[tt]] >= h[i]) tt -- ;
            l[i] = q[tt];
            q[ ++ tt] = i;
        }

        // 求右边界
        tt = 0;
        q[0] = n + 1;
        for (int i = n; i; i -- )
        {
            while (h[q[tt]] >= h[i]) tt -- ;
            r[i] = q[tt];
            q[ ++ tt] = i;
        }

        LL res = 0;
        for (int i = 1; i <= n; i ++ )
            res = max(res, (LL)h[i] * (r[i] - l[i] - 1));

        printf("%lld\n", res);
    }

    return 0;
}
456. 132模式 单调栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int right = INT_MIN;
        stack<int> stk;
        for (int i = nums.size() - 1; i >= 0; i -- ) {
            if (nums[i] < right) return true;
            while (stk.size() && stk.top() < nums[i]) {
                right = max(right, stk.top());
                stk.pop();
            }
            stk.push(nums[i]);
        }
        return false;
    }
};
456. 132模式 暴力解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n=nums.size();
        int base=nums[0];
        for(int j=1;j<n;j++)
        {
            for(int k=n-1;k>j;k--)
                if(base<nums[k] && nums[k]<nums[j]) return true;
            base=min(base,nums[j]);
        }
        return false;     
    }
};