习题1. 131. 直方图中最大的矩形

(做这题之前建议先 回顾 Acwing 830. 单调栈 )

思路:

我们可以以当前的高度, 向左右两边扩展 (只高度>= 自己的 面积才能加进来)
\
所以这样子问题就转换成为 :
当前这个数左边第一个比它小的数
当前这个数右边第一个比它小的数
\
所以我们就可以进行操作了

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =  1e5+10;
int h[N],l[N],r[N];
stack<int> stk;
int main()
{
    int n;
    while(cin>>n)
    {
        if(n == 0)
            break;
        for(int i = 1; i<=n ; i++)
            scanf("%d",&h[i]);

        h[0] = h[n+1] = -1; ///控制边界

        stk.push(0);///控制边界

        for(int i= 1; i<=n ; i++)
        {
            while(h[stk.top()] >= h[i]) stk.pop(); ///单调栈左边找最小的应用
            l[i] = stk.top();
            stk.push(i);
        }

        while(!stk.empty()) stk.pop();

        stk.push(n+1);
        for(int i=n; i>0 ;i --)
        {
            while(h[stk.top()] >= h[i]) stk.pop(); ///数组反过来求 一遍单调栈左边做小的 便是右边最小的了
            r[i] = stk.top();
            stk.push(i);
        }

        long long ans = 0;
        for(int i=1; i<=n ; i++ )
        ans = max(ans,(ll) h[i]*(r[i] - l[i] - 1)); ///计算面积

        cout<<ans<<endl;
    }
    return 0;
}

这是菜鸟(是本人)的话

我是先做完了单调栈的代码,才过来看这题的,cf分数已经1300了
\
考虑这题的时候,的确努力的在往单调栈这边靠,
\
因为没怎么懂单调栈,所以我就一直卡在 用高度大的去和高度小的去计算 ? 无可厚非
\
我脑子里一个 擎天柱的想法把我给扼杀了 也就是 如果一个很高很高的 那么如果被小的限制了,那么就wa了
\
正是因为这个想法让我的思路偏向dp了
\
对于每一个f[i] (表示当前的最大面积) max(和自己小的去交集,本身自己的面积)

但是还是感觉不行,就是感觉这个状态转移错了,因为他既能被后面的影响也可以被前面的,同时做法好像是o n^2的 所以就摒弃了

最后还是选择看y总,只能说我的思路就差一步了,走偏了,应该是大定小,而不是大去依赖小

没想到最后还是转换成 (左边第一个最小的模型)