一个矩形用了 $h$ 列、高 $H$ 行，它只要求"这 $h$ 列在这 $H$ 行里全是空的"，具体是哪 $h$ 列无所谓。所以只要知道

高度至少为 $H$ 的列一共有几列

就够了。

列可以任意交换，等价于说：任意一列子集都能被聚到一起变成连续的若干列。所以「选一个不覆盖障碍物的矩形」等价于

选一个行区间 $[r_1,r_2]$，把所有在这个行区间内全是 0 的列都选上（多选不亏），面积 $=(r_2-r_1+1)\times(\text{这样的列数})$。

于是枚举矩形的下边 $r_2$，同时维护每一列上"以 $r_2$ 结尾的连续 0 的个数" $h_j$。对某个高度 $H$，能用的列正是满足 $h_j\ge H$ 的那些；把 $h$ 从大到小排序后，第 $i$ 大的 $h$ 乘上 $i$，就是"高度至少为这个 $h$ 的列有 $i$ 列"时能得到的面积，对所有 $i$ 取最大值即可。