1. 直方图中最大的矩形

本题很难！
大家先看下AC代码。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int h[N], stk[N], l[N], r[N];
void get(int bound[N])
{
    int tt = 0;
    h[0] = -1;
    for (int i = 1; i <= n; i ++ )
    {
        while (h[stk[tt]] >= h[i]) tt -- ;
        bound[i] = stk[tt];
        stk[ ++ tt] = i;
    }
}
int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; i ++ ) cin >> h[i];
        get(l);
        reverse(h + 1, h + 1 + n);
        get(r);
        LL res = 0;
        for (int i = 1, j = n; i <= n; i ++, j -- )
            res = max(res, h[i] * (n + 1 - l[j] - r[i] - 1ll));
        cout << res << endl;
    }
    return 0;
}

大概3个月前刷过这道题，现在拿回来讲下。
用我们的res记录最大值，每次求出宽度，l,r。
这里求l数组和r数组就用了我们单调栈的思路。
第一步如果不满足那就弹出

while (h[stk[tt]] >= h[i]) tt -- ;

第二步把这个数值存入。

bound[i] = stk[tt];

最后一步把数插进栈。

stk[ ++ tt] = i;

好最后res取一个max就好了。
当然推荐大家去看y总的讲解h，免费的。

接下来是第二题
2. 滑动窗口的最大值

虽说本题可以用deque做，但这里我们讲一下模拟队列做法。

class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> ans;
        int q[100010];
        int tt = 0, hh = 0;
        for(int i = 0; i < nums.size(); i ++)
        {
            if(hh <= tt && i - q[hh] >= k) hh ++;
            while(hh <= tt && nums[q[tt]] <= nums[i]) tt --;
            q[ ++ tt] = i;
            if(i >= k - 1) ans.push_back(nums[q[hh]]);
        }
        return ans;
    }
};

AC 代码在此。
我们说下思路。
本题跟滑动窗口那题一样，只需要判断队头是否滑出窗口然后维护就好了，具体见上期分享。

好了今天的作业讲解就到这里了，再见！

这里是@cht的全部分享
再见！